2

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

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)时间来找出总和的算法。现在，如果我对所有起点进行排序并将此处建议的答案应用于每个点查找数字范围交点，我将得到 O(N^2) 解决方案。除了集合之外，我可能需要什么样的数据结构有什么线索吗？谢谢！

4

5 回答 5

4

为每个区间 [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)，不需要任何花哨的数据结构。

于 2013-09-30T07:18:51.797 回答
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)1中做到这一点，因此步骤 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

将 print4来自这些重叠：

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

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

1实际上，Fenwick 树在O(log M)时间上进行计数，其中M是区间中不同值的最大可能数量。请注意，M <= 2n因为只能有那么多不同的值。所以说 Fenwick TreeO(log n)及时计算也是正确的。

于 2013-09-30T03:58:24.507 回答
1

快速的想法：首先对间隔进行排序。现在检查您的间隔，将每个间隔添加到按端点排序的最小堆中。对于每个间隔，从堆中删除小于该间隔起点的所有内容。堆中剩余的每个端点都代表一个在此间隔之前开始并与它重叠的间隔，因此将 an 增加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

我还没有测试过这个，但它似乎至少是合理的。

于 2013-09-30T04:03:47.580 回答
0

这可以简单地使用贪婪技术来完成。只需按照以下步骤操作：

根据起点对区间进行排序从最低起点到最高点迭代计算大于或等于当前起点的先前端点的数量。增加当前终点的计数。

于 2013-09-30T07:00:57.957 回答
0

保罗的回答真的很聪明。如果是面试，我想我不会想出这个主意。这里我有另一个版本，也是 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”）就是这个新的间隔带来的重叠数量。更新结果后，我们将新到来的间隔的端点添加到堆中。

于 2017-11-03T04:56:55.673 回答