How to find the maximal number of these intervals that have a common point?

Question

I have been reviewing algorithms, this is question from Anany Levitin's algo book..

You have a list of n open intervals (a1, b1), ... , (an, bn) on the real line. (An open interval (a, b) comprises all the points strictly between its endpoints a and b, i.e., (a, b)= (xi a< x < b}.) Find the maximal number of these intervals that have a common point. For example, for the intervals (1, 4), (0, 3), ( -1.5, 2), (3.6, 5), this maximal number is 3. Design an algorithm for this problem with a better than quadratic time efficiency.

Can any one help me forming an algorithm for it or suggest any resources on the internet..

Thanks , Hareendra

Answer 1

One way to approach this would be as follows: suppose that you were to line up all the intervals on the real number line. Starting from the far left, scan across the intervals. Each time you enter an interval, increment a counter of the number of active intervals, and each time you leave one, decrement the counter. The maximum value of the counter over the course of this process is then the number you're looking for.

To implement this, sort all of the start and end points of the intervals (together) into a giant list of length 2n that contains the start and end points of all the segments as they appear. Then, scan the list from left to right updating the counter based on the points you find (+1 for start points, -1 for end points). Sorting takes O(n log n) time and the scan takes O(n) time for a total of O(n log n) time.

Hope this helps!

Answer 2

Sort into Starts[] and Ends[].

i = 0; j = 0; max = 0; total = 0;

while ( i < n ) {
  if ( Starts[i] < Ends[j] ) {
    i++;
    total++;
    if ( total > max ) max = total;
  } else if ( Ends[j] < Starts[i] ) {
    j++;
    total--;
  } else {
    i++;
    j++;
  }
} // while

Answer 3

1. Sort the intervals by their starting time.
2. Create a priority queue sorting by ending time.
3. Each time before adding a new interval to the queue, poll out all intervals has no overlap with this.

4. The queue size will be the overlapped intervals in a time.

   private Interval solution(Interval[] intervals) {
       Arrays.sort(intervals, (a, b)->{
          return a.start - b.start;
       });
   
       PriorityQueue<Interval> pq = new PriorityQueue<Interval>((a,b)->{
           return a.end - b.end;
       });
   
       int start = 0, end = 0;
       int freq = 0;
       for(Interval i: intervals){
           while(!pq.isEmpty() && i.start > pq.peek().end){
             pq.poll();
           }
           pq.offer(i);
           if(pq.size() > freq){
              freq = pq.size();
              start = i.start;
              end = pq.peek().end;
           }
       }
       return new Interval(start, end);
   }