K'th Min From a set of intervals

user_724109 0
Viewed 61

You have given a set of intervals like {2,7} , {3,8}, {9,11} , {-4,-1} so on. The question is to find the k'th min from these set of intervals.

Also the duplicates are counted twice. For example if intervals are {1,4} and {2,6} and k = 3 then the answer is 2 because if we flatten the intervals and sort merge them then we get the sequence

 1,2,2,3,3,4,4,5,6

Where 3rd min is 3.

There can be a lot of ways to solve this problem. However I am struggling to find the one with minimum time / space complexity.

min data-structures memory time-complexity algorithm
1 Answers
  1. Flat the intervals.
  2. Sort the flatten sequence.
  3. Iterate over the sorted sequence, until you find the k-th element, while ignoring duplicate values.

Now let's do some analysis, where we set N the number of total numbers present in your intervals and M the average number of duplicate values a number will have (will be 1 for a unique flatten sequence).

Space Complexity:

O(N)

where you could do better, if you have many duplicate elements, by iterating over the flatten sequence, while discarding the duplicate elements.

Time Complexity:

O(k*M + NlogN)

  • Flattening takes O(N)
  • Sorting takes O(NlogN)
  • Iteration takes O(k*M)
user_24113200
Related