CODEWITHSUNDEEP
algorithmdata-structuresnumbersset
Abhishek Marrivagu
Abhishek Marrivagu

Reputation: 129

Middle element from a disjoint set of sorted intervals

We want to find the middle element in the given intervals of numbers.

Suppose we are given a set with 3 intervals which are { [1, 10], [20, 30], [35, 40] }. (The intervals are always disjoint).

If we combine all intervals we get 25 numbers which are given below:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 35, 36, 37, 38, 39, 40

The answer is the middle element which is the 13th element which is 22. So the answer is 22.

But each of the intervals can be of range [1,1000000000]. Given the intervals you are to calculate the middle element.

Is there any data structure or algorithm to code this ?

Note : If there are 'n' number of elements and 'n' is even the answer can be the (n/2)th element.

Example : if there are total four elements if we combine intervals then the 2nd element is the answer

Upvotes: 2

Views: 117

Answers (1)

Gray_Rhino
Gray_Rhino

Reputation: 1303

First of all, when we combine the intervals in your example we get 27 numbers and the middle element (median) is the 14th element which is 23. As גלעד ברקן mentioned in the comment the fastest way to achieve what you want is O(n) where n is the number of intervals (n = 3 in your above example). Here's Python code with explanation

# I assume your intervals are list in a list
def findMedian(intervals):
   numberOfElements = 0

   for interval in intervals:
      numberOfElements += interval[1] - interval[0] + 1 # We count how many numbers are in each interval

   middleElementPosition = numberOfElements//2 
   median = 0

   # At this point we know how many numbers are in the intervals and the position of the middle number
   # So we go and find the middle number 
   for i in range(len(intervals)):
      if middleElementPosition > (intervals[i][1] - intervals[i][0] + 1):
         middleElementPosition -= (intervals[i][1] - intervals[i][0] + 1)
      else:
         median = intervals[i][0] + middleElementPosition
         break # once we find median we leave loop

    return median

Note that we are mainly working with the number of elements, not the elements themselves. All that matters is the number of intervals.

Upvotes: 1

Related Questions