范围内每个间隔的最大重叠次数

Question

给定间隔列表

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

其中，每个列表的第一个元素是开始时间，第二个元素是结束时间。

我们看到0- 30与所有其他5个区间重叠，而所有其他间隔仅与另一个区间重叠一次，因此重叠的最大数目为5。

我在网上看到了很多关于从找到会议或火车所需的最少数量的平台或房间的答案

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

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

但是我不知道这些algo是如何适用于这个问题的，因为我已经尝试了algo，它们将返回这个示例输入列表所需的平台和空间数2，因为它们将试图在特定时间找到最大重叠数，但我想知道在整个时间间隔内可以发生的最大重叠数。

下面是我的蛮力方法，它可以工作，但是如果可能的话，我如何将运行时最小化到O(nlogn)？

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

让我们修复一个间隔[L, R]。考虑任意间隔的[a, b]。在以下情况下，这两个间隔不重叠：

1. b < L或
2. a > R

请注意，任何区间最多都满足这两个条件中的一个。因此，对于[L, R]区间，它重叠的间隔数等于N - c1 - c2 - 1，其中N是总间隔数，c1是满足条件1的间隔数，c2是满足条件2的间隔数。

如何快速找到c1和c2？

如果我们有一个按其右边框排序的所有间隔的列表，则c1等于第一个区间的位置(按排序顺序排列)，因此其右边框不小于L。我们可以用二进制搜索找到它。

通过对按左边框排序的间隔列表进行二进制搜索，我们可以找到c2 (它的间隔数减去第一个间隔的位置，使其左边框大于R)。

我们需要在这里对两个大小为N的列表进行排序，并在它们上运行2个二进制搜索( N时间)。因此，时间复杂度是O(N * log N)。

Answer 2

下面是我的问题代码，这个概念有效，但是没有检查二进制搜索的边界条件。

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