CareerCup

Assuming the intervals begin and end at integral values, sort the intervals using their begin values.
Using an auxiliary array aux[n], where n is the maximum end value of all the intervals

counter = 0;
for (i = 1..n)  {
 if an interval opens at i, counter++;
 if an interval closes at i, counter--;
 aux[i] = counter
}

Go over aux[] array to find out the maximum value. Do a reverse lookup to find the list of intervals that contain the maximum value of aux[] array.

Let S = {[a1,b1],[a2,b2],...,[an,bn]} be the set of intervals.

1. Create the following array:
array = {(a1,start),(b1,end),(a2,start),(b2,end),...,(an,start),(bn,end)} (the first coordinate is a number and the second coordinate is a label).
2. Sort the array according to lexicographic order where start<end (the first coordinate is a number).
3. Initialize count=0 (count will mark the current number of overlapping intervals).
4. Initialize maxCount=0 (maxCount will mark the maximum number of overlapping intervals).
5. Define maxStart (maxStatr will mark the start of the interval with maximum overlapping intervals).
6. Initialize maxInterval = null (maxInterval will mark the interval with maximum overlapping intervals).
7. Iterate over the sorted array (beginning to end):
7.1. Increment count whenever you encounter a value whose label is start (x,start).
7.2. Decrement count whenever you encounter a value whose label is end (x,end).
7.3. If count>=maxCount then set maxStart to the current number value of the array element (the x in (x,label)) and set maxCount=count.
7.4. If the current array element is labeled end and after updating count it equals to maxCount-1 it means that the current array point marks the end of the maximum overlapping interval. So we set maxInterval to the interval (maxStart,current_array_element.x).
8. return maxInterval.

Complexity: O(nlogn) worst-case run-time complexity where n is the number of intervals. Space complexity is O(n) for the additional array.

Java Implementation: snipt.org/Bfjaf0

I understand one common approach is to create an array = {(a1,start),(b1,end),(a2,start),(b2,end),...,(an,start),(bn,end)} (the first coordinate is a number and the second coordinate is a label). Sort the array according to lexicographic order where start

What I don't understand when we create the array, we are essentially separating the start time and end time from each interval. So each start time and end time will lose their identify of which interval they belongs to. When we walk through the array, it would not make sense if we just increment/decrement the count without knowing each coordinate corresponds to which interval. If we use a hashmap and map each coordinate to their interval, there might be issues with duplicate start times and end times.

How should we solve this issue?

public class MaximumOverlap {

    public static void main(String[] args) {

        int[] start = {1, 2, 3, 6};
        int[] finish = {6, 7, 5, 8};

        QuickSort quick = new QuickSort();

        quick.quickSort(finish, 0, finish.length - 1);
        quick.quickSort(start, 0, start.length - 1);

        int s = 0, f = 0;
        int[] count = new int[finish[finish.length - 1] + 1];
        int max = 0;
         int index = 0;
        for (int i = start[0]; i <= finish[finish.length - 1]; i++) {


            count[i] = count[i - 1];
            if (s < start.length && i == start[s]) {
                count[i]++;
                s++;
            }
            if (f < finish.length && i == finish[f]) {
                count[i]--;
                f++;
            }

            if (max < count[i]) {
                max = count[i];
                index=i;
            }
        }

        int k;
        for(k=index;k<count.length;)
        {
           if(count[k]==count[k+1])
           {
               k++;
           }
            else
               break;
        }

        System.out.print("interval start time "+index+" interval end time "+(k+1));

    }
}

why dont we create a node for each interval point. and mark node visited each time you pass by.

Very good question. I often check the Amazon section because they have more questions than other section, not the other thing though.

How about this?

Put all the left bounds and right bound of the ranges into an array A, and
sort the array. Do the following.

max = count = 0;  // max is the maximum number of overlaps
for (i = 0; i < A.size; i++) { 
    if (A[i] is a left bound) {
        count++;
        if (count > max) mx = count;
    }
    else 
        count--;
}

You have already asked the same question id=5131269318901760, haven't you?