PROBLEM STATEMENT
You will be given a list of ranges of numbers. The numbers from the given
ranges will be compiled into one huge list and then sorted in ascending order.
Note that the sorted list may contain duplicate values. Given a position
(0-based) in the sorted list you will return the number at that position. For
example,
[low,high] means the set of numbers between low and high, inclusive
Ranges = [0,5],[1,5],[0,4],[1,3]
First we compile all the numbers into one huge list:
{0,1,2,3,4,5,1,2,3,4,5,0,1,2,3,4,1,2,3}
Next we sort the list:
{0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5}
If asked for the value at position 7 you would return 2. If asked for the
value at position 0 you would return 0. If asked for the value at position 2
you would return 1. Notice that there are duplicate values in the sorted list.
In the problem you will have two arrays representing the ranges. The ranges
used above would be given as:
lowerBound = {0,1,0,1}
upperBound = {5,5,4,3}
This input would signify ranges [0,5],[1,5],[0,4],[1,3]. In other words range
K has lowerBound[K], and upperBound[K] as its lower and upper bounds
respectively.
Create a class RangeSort that contains the method valueAt, which takes an int[]
lowerBound, an int[] upperBound, and an int position, and returns an int
representing the value at the given position in the sorted list.
DEFINITION
Class: RangeSort
Method: valueAt
Parameters: int[], int[], int
Returns: int
Method signature (be sure your method is public): int valueAt(int[]
lowerBound, int[] upperBound, int position);
NOTES
- Range K will have lower inclusive bound lowerBound[K] and upper inclusive
bound upperBound[K]
- Do not try to put all of the numbers into a huge array in order to sort them
since it will not work on larger test cases
- Given a range like [A,A] there is only one number in the range, A. For
example, [8,8] = {8}.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
Let N = the total number of numbers contained in all of the ranges put together
- lowerBound will contain between 1 and 50 elements inclusive
- lowerBound and upperBound will contain the same number of elements
- lowerBound[K] will be less than or equal to upperBound[K] (lowerBound[K] <=
upperBound[K])
- Each element of lowerBound will be between -10000000 and 10000000 inclusive
- Each element of upperBound will be between -10000000 and 10000000 inclusive
- position will be between 0 and N-1 inclusive
EXAMPLES
1) lowerBound = {0,1,0,1}
upperBound = {5,5,4,3}
position = 7
First we compile all the numbers into one huge list:
{0,1,2,3,4,5,1,2,3,4,5,0,1,2,3,4,1,2,3}
Next we sort the list:
{0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5}
The value at position 7 is 2.
Method returns 2.
2) lowerBound = {0,1,0,1}
upperBound = {5,5,4,3}
position = 0
Same list as example 1. At position 0 the value is 0.
Method returns 0.
3) lowerBound = {0,1,0,1}
upperBound = {5,5,4,3}
position = 2
Same list as example 1. At position 2 the value is 1.
Method returns 1.
4) lowerBound = {-10,-10,-10,-10}
upperBound = {10,10,10,10}
position = 20
Method returns -5.
5) lowerBound = {-10,-10,-10,-10}
upperBound = {10,10,10,10}
position = 27
Method returns -4.
6) lowerBound = {-10000000,-10000000,-10000000,-10000000,-10000000}
upperBound = {-10000000,-5000000,0,5000000,10000000}
position = 3500000
Method returns -9125001.
7) lowerBound = {9}
upperBound = {9}
position = 0
Method returns 9.