寻找与最多数量的区间相交的区间：给出许多区间 [ai, bi]，找到一个与最多数量的区间相交的区间。

Question

寻找与最多数量的区间相交的区间：给出许多区间 [ai, bi]，找到一个与最多数量的区间相交的区间。

algorithmdata-structures

8

给定许多区间[ai, bi]，找到与最多数量的区间相交的区间。我们能以O(nlogn)或更快的速度完成吗？我只能想到一个n^2的方法。

- Peter

1

http://en.wikipedia.org/wiki/Interval_tree - dlev

可能是重复的问题：给定一组区间，找到具有最大交集数量的区间。 - itsadok

6个回答

4

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

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

- ElKamina

2

根据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;
}

- Happier

1

如果ai和bi的值不是小于N的整数，则可以通过对所有不同的ai和bi值的列表中的索引进行排序来减少它们。给定包含所有不同的ai和bi的输入“list”。在C#中，排序后的索引为：

int[] index = Enumerable.Range(0, list.Count).OrderBy(i => list[i]).ToArray();

通过反转该排列，然后可以为每个ai和bi分配从0到N-1的值。

int[] values = invertPermutation(index);

ai可以替换为values [location_of_ai_in_List]

现在假设新的ai和bi可以使得＜N，那么有一个巧妙的技巧可以在O（N）中找到最大重叠间隔，以及可以快速响应一些其他查询。

1.声明一个N + 1元素的数组：

int [] sum = new int [N + 1];

2.对于每个区间执行：

sum [ai] ++; sum [bi + 1]--;

//由于我们在O（1）中处理每个区间，因此此步骤的总复杂度为O（N）。

聚合:

for (int i = 1; i <= N; i++) { sum[i] += sum[i - 1]; }

//这是一个O(N)的步骤。

找到sum[k]最大的位置k。
遍历新区间[ai, bi]，并找到第一个包含位置k的区间（即ai <= k && k <= bi）。

这个区间[ai, bi]是一个解决方案，它与所有其他区间相交的次数为“sum[k] - 1”（不计算它本身）。

- RobertB.

0

如果ai，bi是小整数（例如16位数字），则一种替代区间树的方法是：

创建一个具有N个值的数组A，其中N大于max(bi)
将数组中的所有值清零
循环遍历区间并更改A[ai]:=A[ai]+1, A[bi+1]:=A[bi+1]-1
设置x=0
循环遍历数组计算x:=x+A[j]，并查找最大值的x

迭代j时的x值给出与点j相交的区间数量，因此找到最大值可以得到相交最多的点。

这需要O(N+n)个周期，因此仅在n>N的情况下对您的应用程序有用。

（严格来说，这并没有回答问题，因为它找到了相交最多的点。但是，您应该能够扩展此方法以找到相交最多的区间。）

- Peter de Rivaz

-1

你可以在n中完成它。

[最小的ai，最大的bi]

所以。。。

varmin = interval[0]['begin']
varmax = interval[0]['end']
foreach( interval as rang ) {
  varmin = min( rang['begin'], varmin )
  varmax = max( rang['end'], varmax ) }
newrange = array('begin'=>varmin,'end'=>varmax)

- DanRedux

我认为你应该选择一个现有的范围而不是定义新的范围。 - Gumbo

为什么？他说“找到范围”，而不是“扩展范围以包括新范围”。 - DanRedux

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- PengOne · Accepted Answer

假设已经给定区间为(a1,b1), ..., (an,bn)，制作一个长度为2n的排序数组，其中通过以下方式解决平局:

如果 ai = aj，则当且仅当 bi < bj 时，先将 ai 排在前面。
如果 bi = bj，则当且仅当 ai < aj 时，先将 bi 排在前面。
如果 ai = bj，则先将 ai 排在前面。

将每个点标记为 a 或 b (可以使用长度为2n的二进制数组来完成此操作)。遍历数组，并跟踪与给定点相交的区间数(即 a 的累加和减去 b 的累加和)。在最大重叠的区间发生的地方，遇到的最大数字即为最大相交数量。

由于需要对区间进行排序，因此时间复杂度为O(n log n)。