给定许多区间[ai，bi]，找出一个与最多区间数相交的区间

Question

给定许多区间ai，bi，找出与最多区间数相交的区间。我们能在O(nlogn)或更好的环境中做到这一点吗？我只能想到n^2的方法。

Answer 1

假设间隔以(a1,b1), ..., (an,bn)的形式给出。创建一个长度为2n的有序数组，其中平局被

如果为ai = aj，则将ai放在第一当bi < bj

• if bi = bj时，然后将bi放在第一当ai < aj

• if ai = bj，然后将ai放在第一

<>F217

将每个点标记为a或b (可能需要保留一个长度为2n的二进制数组来执行此操作)。遍历数组，跟踪与给定点接触的间隔数(运行的a总数减去运行的b总数)。遇到的最大数量发生在重叠最多的时间间隔。

由于时间间隔的排序，这是O(n log n)。

Answer 2

使用区间树：http://en.wikipedia.org/wiki/Interval_tree。

如果使用中心区间树，复杂度为O(nlogn + m)，其中m是交叉点的总数(最坏情况下的m=n^2)。

Answer 3

根据PengOne的回答，我做了一个简单的实现，使用两个n排序数组而不是2n数组。

1) Construct two n arrays, one is sort by ai, another is sort by bi.
   make sure that if ai==aj, then bi<bj, but i before j, the same as b-array.
2) Walk through the b-array for each b, Do a binary search in a-array to find 
   index, make sure a[index]<=b<a[index+1]
3) find the max(index - i + 1), the the bi is the point we need.

代码

public int getPoint(List<Interval> intervals) {
    // validation
    if (intervals == null || intervals.size() == 0) {
        return 0;
    }
    List<Interval> sortA = sortByA(intervals);
    List<Interval> sortB = sortByB(intervals);
    int max = 0;
    int maxPoint = sortB.get(0).b;
    for (int i = 0; i < sortB.size(); i++) {
        Interval interval = sortB.get(i);
        // find B in sortA.
        int index = search(sortA, interval.b);
        int count = index - i + 1;
        if (count > max) {
            max = count;
            maxPoint = sortB.get(i).b;
        }
    }
    return maxPoint;
}