Last Updated: 2 Feb, 2021

Kth Smallest Integer In Ranges

Moderate

Asked in company

Solve now

Problem statement

You are given a list of ‘N’ ranges of integers. A range can be represented as (‘start’, ‘end’) where ‘end’ >= ‘start’ and all the integers between ‘start’ and ‘end’ (inclusive) belong to that range.

You need to answer ‘M’ independent queries. In each query, you are given an integer ‘K’ and you need to find the Kth smallest integer of the sequence formed by all the distinct integers of these ‘N’ ranges.

Example:

Let ‘N’= 5,  ‘ranges’ be [(5, 7), (6, 8), (3, 6), (10, 11), (15, 15)], ‘M’ = 3 and these 3 queries are given by array ‘queries’ = [4, 2, 8].
Then the sequence formed by distinct integers present between these ranges in ascending order is [3, 4, 5, 6, 7, 8, 10, 11, 15].
So, 
The 4th smallest element of this sequence is 6.
The 2nd smallest element of this sequence is 4.
The 8th smallest element of this sequence is 11.

Note:

If the sequence has less than K integers then the answer will be -1.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The description of ‘T’ test cases follows-:

The first line of each test case contains two space-separated integers  ‘N’ and ‘M’ representing the number of ranges and number of queries respectively.

Next ‘N’ lines of the test case contain two space-separated integers, ‘start’ and ‘end’, denoting the starting and the ending point of the ith range.

The last line of the test cases contains ‘M’ space-separated integers representing ‘M’ queries.

Output format :

For each test case, print a line consisting of M space-separated integers where the ith integer represents the answer of the ith query.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function. 

In the given function, you need to return an array consisting of ‘M’ integers where the ith integer is the answer of the ith query. In a given function the parameter ‘ranges’ is the list of ‘N’ lists of 2 integers representing ‘N’ ranges where the 1st element of each list represent 'start' and the second element represent 'end' of the range,  and parameter ‘queries’  which is the list of ‘M’ Integers representing queries.

Constraints:

1 <= T <= 50
1 <= N <= 10^4
1 <= M <= 10^4
1 <= K <= 10^9
1 <= start <= end <= 10^9

Where ‘T’ is the total number of test cases, ‘N’ is the number of ranges, ‘M’ is the number of queries, ‘K’ is the integer in the query, and ‘start’ and ‘end’ represent the first and the last integer of ranges,

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Appraoch: We will create a list ‘sequence’ and push all distinct elements of these ranges in it. We then sort this list in ascending order. After that, each of the ‘M’ queries can be answered in constant time.

Algorithm:

Create a list of integers ‘SEQUENCE’.
Create a HashMap to track whether an integer is already present in the list ‘SEQUENCE’ or not.
Iterate over the list ‘RANGES’ and do the following for each range in that list
- Run a loop where ‘j’ ranges from start to end of the range, and for each ‘j’ if it is not present in HashMap then add it to HashMap and in the list ‘SEQUENCE’.
Sort the array sequence in ascending order.
Create a list ‘RESULT’ of size ‘M’.
Run a loop where ‘i’ ranges from 0 to M - 1 and in each iteration do following
If ‘QUERIES[i]’ is greater than size of list ‘sequence’ then assign RESULT[i] = -1
Otherwise assign RESULT[i]:= SEQUENCE[k - 1].
Return ‘RESULT’.

Solve now

02 Approach

Approach: First, we need to sort the ranges based on lower limits in non-decreasing order and if the lower limits of ranges are the same, sort them according to higher limits in non-decreasing order.

Now we need to merge overlapping intervals. This can be done easily by iterating over the sorted list of ranges and checking whether the ‘start’ of the range is smaller or equal to the maximum value of ‘end’ of all the ranges before it.

After that, we can answer each of the M queries by simply iterating over the list of given ranges.

Algorithm:

Sort the given list of ‘RANGES’
Create another list ’MERGERANGES’.
Initialize an integer variable ‘CUREND’ by a negative infinite value.
Create another integer variable ‘CURSTART’
Iterate over the list ‘RANGES’ and for each range do the following.
- If ‘START’ of the range is greater than ‘CUREND’, then push range (CURSTART, CUREND) (except when curEnd is negative infinity) in the list ‘MERGERANGES’. and then update ‘CURSTART’ by ‘START’ of the current range.
- Update ‘CUREND’ by the max of its current value and ‘END’ of the current range.
Push range (CURSTART, CUREND) in the list ‘MERGERANGES’.
List ‘MERGERANGES’ will now have a non-overlapping and sorted list of ranges.
Create a list ‘RESULT’ of size ‘M’ and fill it with -1.
Run a loop where ‘i’ ranges from 0 to ‘M’ and for each query ‘i’ do the following.
- Initialize a variable ‘COUNT’ := 0.
- Iterate over the list ‘MERGERANGES’ and for each range increment ‘COUNT’ by the size of that range. If ‘COUNT’ >= ‘QUERY[i]’, then the answer of this query lies in this range, and it will be (COUNT - ‘QUERY[i]’)th element of that range from ‘end’. Assign it to the ‘RESULT[i]’.
Return ‘RESULT’.

Solve now

03 Approach

Approach: First, we need to sort the ranges based on lower limits in non-decreasing order and if the lower limits of ranges are the same, sort them according to higher limits in non-decreasing order.

Now we need to merge overlapping intervals. This can be done easily by iterating over the ranges and checking whether the ‘start’ of the range is smaller or equal to the maximum value of ‘end’ of all the ranges before it.

After that, for each range, we find out what will be the position of ‘start’ and ‘end’ of that range in the sequence formed by arranging all distinct elements of these ‘N’ ranges in ascending order. Queries can be answered using binary search after this.

Algorithm:

Sort the given list of ‘RANGES’
Create another list ’MERGERANGES’.
Initialize an integer variable ‘CUREND’ by a negative infinite value.
Create another integer variable ‘CURSTART’
Iterate over the list ‘RANGES’ and for each range do the following.
- If ‘START’ of the range is greater than ‘CUREND’, then push range (CURSTART, CUREND) (except when curEnd is negative infinity) in the list ’MERGERANGES’. and then update ‘CURSTART’ by ‘start’ of the current range.
- Update ‘CUREND’ by the max of its current value and ‘END’ of the current range.
Push range (CURSTART, CUREND) in the list ’MERGERANGES’.
List ’MERGERANGES’ will now have a non-overlapping and sorted list of ranges.
Let ‘P’ be the size of ’MERGERANGES’.
Create a list ‘POSITION’ of size ‘P’ such that POSITION[i] will be the position of the start element of ’MERGELIST[i]’, It can be calculated easily by counting the total number of integers in ranges before it.
Create a list ‘RESULT’ of size ‘M’ and fill it with -1.
Run a loop where ‘i’ ranges from 0 to ‘M’ and for each query ‘i’ use binary search as follows to find its answer.
- Initialize ‘LOW’ := 0 and ‘HIGH’ := P-1.
- Run a while loop till ‘HIGH’ >= ‘lo‘LOW’w’.
- Initialize ‘MID’ = (‘LOW’ + ‘HIGH’)/2.
- If ‘QUERY[i]’ is in between POSITION[MID] and POSITION[MID] + (MERGELIST[MID][1] - MERGELIST[MID][0]), then ‘RESULT[i]’ will be the (QUERY[i] - POSITION[MID])th element of the range ’MERGELIST[MID]’,
- If ‘QUERY[i]’ is less than POSITION[MID], then its answer lies between ranges (LOW, MID - 1)
- Otherwise, the answer lies between ranges (HIGH, MID + 1)
Return ‘RESULT’.

Solve now