UnionOfIntervals
SRM 277 · 2005-12-17 · by lovro
Problem Statement
Given a list of integers, find the n-th smallest number, i.e., the number that appears at index n (0-based) when they are sorted in non-descending order. The numbers will be given in intervals. For example, the intervals (1, 3) and (5, 7) represent the list of numbers { 1, 2, 3, 5, 6, 7 }. A number may be present in more than one interval, and it appears in the list once for each interval it is in. For example, the intervals (1, 4) and (3, 5) represent the list of numbers { 1, 2, 3, 3, 4, 4, 5 }.
The intervals will be given as two
Notes
- n is 0-based, meaning that the first element is indexed 0.
- A sequence is sorted in non-descending order if and only if for each pair of indices i and j, where i is smaller than j, the element at position i is less than or equal to the element at position j.
Constraints
- lowerBound will contain between 1 and 50 elements, inclusive.
- upperBound will contain the same number of elements as lowerBound.
- Each element of lowerBound and upperBound will be between -2,000,000,000 and 2,000,000,000, inclusive.
- The i-th element of lowerBound will be less than or equal to the i-th element of upperBound.
- n will be a non-negative integer less than the total number of elements in the list, but no greater than 2,000,000,000.
{ 1, 5 }
{ 3, 7 }
4
Returns: 6
The numbers are 1, 2, 3, 5, 6 and 7. The number at index 4 is 6.
{ 1, 3 }
{ 4, 5 }
3
Returns: 3
{ -1500000000 }
{ 1500000000 }
1500000091
Returns: 91
Watch out for overflow errors.
{ 1999999998 }
{ 2000000000 }
1
Returns: 1999999999
{ -456, -82481, 484, 399 }
{ 19342, 200, 8484, 1000 }
44444
Returns: -38037
Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class UnionOfIntervals with a public method int nthElement(vector<int> lowerBound, vector<int> upperBound, int n) · 95 test cases · 2 s / 256 MB per case