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]])));

Seems like a duplicate of Find all disjointed intersections in a set of vertical line segments — Redu
– Redu, Commented Nov 1, 2016 at 19:53
@Redu similar problem it seems, but their algo also runs in O(n^2) time, feel like their algo is way too complicated — Ohhh
– Ohhh, Commented Nov 1, 2016 at 20:06
Yes it's a little bit convoluted but that's because what you ask requires more than a simple reducing of intersections. That's also not O(n^2) but something less (the inner reduce only works for the items those haven't intersected previously), though can not make sure about it's time complexity. I would recommend you to read the accepted answer's explanation part and check the last code snippet which is mush easier to understand. — Redu
– Redu, Commented Nov 1, 2016 at 20:22

user3386109 · Accepted Answer · 2016-11-01 20:12:29Z

3

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

b < L or
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).

edited Nov 1, 2016 at 20:12

user3386109

35k7 gold badges52 silver badges69 bronze badges

answered Nov 1, 2016 at 19:42

kraskevich

18.6k4 gold badges37 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ohhh Over a year ago

logically, it makes sense, thanks, let me try to implement the algo

apadana Over a year ago

Smart answer! There are other solutions too (like using a counter and sorting both start and end at the same time), but this one was very logical.

Ohhh · Accepted Answer · 2016-11-01 21:17:10Z

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);
}

Collectives™ on Stack Overflow

Maximum number of overlapping for each intervals during its range

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related