Maximum number of overlapping for each intervals during its range

Question

Given the interval list

[[0,30],[1,5],[6,10],[11,15],[16,20], [21,25]]

Where the first element for each list is the start time, and the second element is the end time.

We see that 0 - 30 overlaps with all other 5 intervals, and all the other interval only overlaps once with another interval, so the maximum number of overlapping is 5.

Im seeing alot of answers online about finding the minimum number of platform or room needed for conference or train from

http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/

http://www.zrzahid.com/maximum-number-of-overlapping-intervals/

But I don't see how those algo applies to this question, as I have tried the algo and they will return 2 for the number of platform and room needed for this example input list, as they will try to find the maximum number of overlap at a particular time, but I want to know the maximum number of overlap that can happen during the entire time interval.

Below is my brute force approach, and it works, but how can I minimize the runtime to O(nlogn) if possible?

function maxNumConflict(intervals) {
    max = 0;
    for (var i = 0; i < intervals.length; i++) {
        tempMax = 0;
        for (var j = i + 1; j < intervals.length; j++) {
            if (overlap(intervals[i], intervals[j])) {
                tempMax++;
            }
        }
        max = Math.max(tempMax, max);
    }
    return max;
}

function overlap(i1, i2) {
    return ((i1[0] >= i2[0] && i1[0] < i2[1])
         || (i2[0] >= i1[0] && i2[0] < i1[1]));
}
console.log(maxNumConflict(([[0,30],[1,5],[6,10],[11,15],[16,20], [21,25]])));

Answer 1

Below is my code for the question, the concept works, but didn't check the boundary condition for binary search.

// nlogn solution
// Solution is not correct, got error boundary condition on binary search, but the concep works
function findMaxOverlap(times) {

    var arrSize = times.length;
    var max = 0;
    var start = [];
    var end = [];

    // Split the times list into start time list and end time list
    for (var i = 0; i < times.length; i++) {
        start.push(times[i][0]);
        end.push(times[i][1]);
    }

    // Sort them
    start.sort(compare);
    end.sort(compare)

    // Find the number of overlapping for each interval
    for (var i = 0; i < arrSize; i++) {
        max = Math.max(max, findMaxHelper(start, end, times[i], arrSize));
    }

    return max;

}

function compare(a,b) {
    if (a < b) {
        return -1;
    } else if (a > b) {
        return 1;
    }
    return 0;
}


function findMaxHelper(startArr, endArr, interval, arrSize) {

    // Num of element that do not overlap with current interval
    var c1 = 0;         // Num of element that has their start time >= current end time 
    var c2 = 0;         // Num of element that has their end time =< current start time 

    c1 = arrSize - binarySearch(startArr, interval[1]);
    c2 = binarySearch(endArr, interval[0]);

    var overlap = arrSize - c1 - c2 - 1;
    return overlap;

}


// Find the index of the element that is >= or =< than time
function binarySearch(arr, time) {

    var low = 0;
    var high = arr.length;
    var mid = high / 2;

    while (low <= high) {
        var mid = Math.round(low + (high - low) / 2);

        if (arr[mid] > time) {  
            high = mid - 1;
        } else if (arr[mid] < time) {
            low = mid + 1;
        }  else {
            return mid;
        }

    }
    return Math.round(low + (high - low) / 2);
}

Answer 2

Let's fix an interval [L, R]. Consider an arbitrary interval [a, b]. These two intervals do not overlap if:

1. b < L or
2. a > R

Note that any interval satisfies at most one of these two conditions. Thus, for the [L, R] interval the number of intervals it overlaps with is equal to N - c1 - c2 - 1, where N is the total number of intervals, c1 is the number of intervals that satisfy the condition 1 and c2 is the number of intervals that satisfy the condition 2.

How to find c1 and c2 quickly?

If we have a list of all intervals sorted by their right border, c1 is equal to the position of the first interval (in sorted order) such that its right border is not less than L. We can find it using binary search.

Using a binary search over the list of intervals sorted by the left border we can find c2 (its the number of intervals minus the position of the first interval such that its left border is greater than R).

We need to sort two lists of size N here and run 2 binary searches over them N times. Thus, the time complexity is O(N * log N).