找到重叠的集合的间隔

Question

所以我有一个包含间隔端点的集合。例如，

Set s = {(1,4),(3,7),(5,8),(14,17),(0,2),(11,14)} 

我需要一种方法来找出有多少重叠间隔。在上述情况下，答案应该是5，因为

(1,4) --> (3,7), (0,2) 
(3,7) --> (5,8),(0,2) 
(5,8) --> 
(14,17) --> (11,14) 

我需要一个算法，需要O(N log N)时间去找出总和。现在，如果我排序所有的出发点，并在每个点Find number range intersection上应用这里建议的答案，我会得到一个O（N^2）解决方案。除了集合之外，我还需要什么样的数据结构？谢谢！

Answer 1

为每个区间[a，b]构建值列表（a，-1），（b，1）。现在，通过对这些进行排序，您可以运行数组，计算每个端点当前打开的间隔数，只需将+1和-1进行聚合即可。

重要的是（b，1）在排序列表中后（b，-1）;因为我们要计算相交点，即使交点是在一个点上。

在这里完成代码。

def overlaps(intervals): 
    es = [] 
    for a, b in intervals: 
     es.append((a, -1)) 
     es.append((b, 1)) 
    es.sort() 
    result = 0 
    n = 0 
    for a, s in es: 
     if s == -1: result += n 
     n -= s 
    return result 

注意，这是平凡的O（n log n），并且不需要任何奇特的数据结构。

Answer 2

首先我从你的例子中假设(0,1)和(1,2)重叠。

顺便说一句，你的例子是不正确，(3,7)不(0,2)

一种方式重叠解决是这样的：

1. 排序根据起点
2. 从最低起点迭代间隔到最高点
   2a。计算比当前起始点更大的以前端点数量或等于。
   2b。添加一个到当前终点的数量。

步骤1在O(n log n)
第2步是遍历所有的时间间隔，而这样做的计数来完成。所以这是O(n * X)其中X是做计数的复杂性。用Fenwick Tree，我们可以在O(log n) 这样做，所以第2步也可以在O(n log n)内完成。

所以整体复杂度是O(n log n)。

伪代码：

def fenwick_tree.get(num): 
    return the sum from counter[0] to counter[num] 

def fenwick_tree.add(num, val): 
    add one to counter[num] 

intervals = [...] 
sort(intervals) # using the starting point as the key 
init_fenwick_tree() 
sum = 0 
count = 0 
for (starting_point, end_point) in intervals: 
    sum = sum + (count - fenwick_tree.get(starting_point-1)) 
    fenwick_tree.add(end_point,1) 
return sum 

Python代码（仅当间隔点是一个非负整数作品）：

MAX_VALUE = 2**20-1 
f_arr = [0]*MAX_VALUE 

def reset(): 
    global f_arr, MAX_VALUE 
    f_arr[:] = [0]*MAX_VALUE 

def update(idx,val): 
    global f_arr 
    while idx<MAX_VALUE: 
     f_arr[idx]+=val 
     idx += (idx & -idx) 

def read(idx): 
    global f_arr 
    if idx <= 0: 
     return 0 
    result = 0 
    while idx > 0: 
     result += f_arr[idx] 
     idx -= (idx & -idx) 
    return result 

intervals = [(1,4),(3,7),(5,8),(14,17),(0,2),(11,14)] 
intervals = sorted(intervals, key=lambda x: x[0]) 
reset() 
total = 0 
for processed, interval in enumerate(intervals): 
    (start, end) = interval 
    total += processed - read(start-1) 
    update(end, 1) 
print total 

将打印4，它来源于这些重叠：

 
(0,2) - (1,4) 
(1,4) - (3,7) 
(3,7) - (5,8) 
(11,14) - (14,17) 

请注意，我们无法获得重叠间隔，因为在最坏的情况下，重新将O(n^2)重叠，这在O(n log n)时间内无法打印。

_{实际上树状数组确实计数在O(log M)时间，其中M在区间不同值的最大可能的数目。请注意0​​，因为只能有很多不同的值。所以说Fenwick Tree在O(log n)时间内进行计数也是正确的。}

Answer 3

快速构思：首先排序你的区间。现在通过你的时间间隔，将每个添加到由端点排序的最小堆中。对于每个时间间隔，从堆中移除小于该时间间隔起点的所有内容。堆中剩余的每个端点都表示一个间隔，该间隔在此间隔之前开始并与其重叠，因此按堆的大小增加一个overlaps。现在将当前间隔添加到堆并继续。

伪代码：

Sort(intervals) 
(firstStart, firstEnd) = intervals[0] 
currentIntervals = MinHeap() 
overlaps = 0 

for each (start, end) in intervals[1:]: 
    remove from currentIntervals all numbers < start 
    overlaps += Size(currentIntervals) 
    HeapPush(end, currentIntervals) 
return overlaps 

我没有测试过这一点，但似乎至少似是而非。

Answer 4

这可以简单地使用贪婪技术来完成。 只要按照下面的步骤：

排序根据起点 迭代从最低起点到最高点 间隔数之前的终点比目前的起点大于或等于的数。 递增当前终点的计数。

Answer 5

保罗的答案真的很聪明。如果是面试，我不认为我能想出这个想法。在这里我有另一个版本，它也是O（nlog（n））。

import heapq 

def countIntervals(s): 
    s.sort() 
    end = [s[0][1]] 
    res, cur = 0, 0 
    for l in s[1:]: 
     if l[0]>heapq.nsmallest(1, end)[0]: 
      heapq.heappop(end) 
     cur = len(end) 
     res += cur 
     end.append(l[1]) 
    return res 

我们维护一个存储即将到来的端点的分钟堆。每当新的时间间隔进入时，我们应该将其起点与最小的终点进行比较。

如果起始点较大，则意味着最小的终点（代表该间隔）不会导致更多的重叠。因此我们将其弹出。

如果起始点较小，则意味着所有终点（相应间隔）与新来的间隔重叠。

然后终点数（“cur”）是这个新来的间隔带来的重叠数。在我们更新结果后，我们将新的间隔端点添加到堆中。