给定一组区间，找到交集最多的区间。

Question

给定一组区间，找到具有最大交集数量的区间（而不是特定交集的长度）。 因此，如果输入为 (1,6) (2,3) (4,11)，则应返回 (1,6)。 有人建议使用区间树以在O(nlogn)中完成此操作，但我在阅读其维基页面后并不理解如何构建和使用区间树。 我相信可以通过进行某种排序和扫描算法来完成它。 如果区间树是唯一选择，请教我如何构建/使用。 谢谢。

- user3216886

---

如果没有预处理，你不能指望在O(n)的时间复杂度下完成这个任务，因为你需要评估所有的区间。 - Vincent van der Weele

抱歉，打错了。本意是O(nlogn)。 - user3216886

Answer 1

不要使用区间树。为每个区间端点创建一个事件，以便每个区间都有一个开始事件和一个停止事件。按顺序处理这些事件。（如果一个度量为零的交集算作交集，则起始时间在停止时间之前，否则停止时间在起始时间之前。）

从区间到数字初始化一个映射C。初始化起始计数s = 0和停止计数t = 0。对于区间i的开始事件进行处理，设置s = s + 1，然后将C(i) = -(t + 1)。对于区间i的停止事件进行处理，设置t = t + 1，然后将C（i）= C（i）+ s。

最后，C将区间映射到它们的交集计数。由于排序，该算法的时间复杂度为O(n log n)；如果只能添加和比较端点，则该运行时间是最优的，通过相当标准的计算几何技术实现。

- David Eisenstat

---

好的，那很快。干得好。（明天才能授予悬赏奖励。） - Sneftel

对于开始事件：C(i)=-1-num_stop_events_so_far，对于停止事件：C(i)+=num_start_events_so_far。这不是更简单吗？ - Evgeny Kluev

@EvgenyKluev 当然可以，为什么不呢？ - David Eisenstat

Evgeny：要精确！那不正确。numIntersections[interval] = StartedEventsTill[end[interval]] - EndedEventsTill[start[interval]]-1 - cegprakash

@cegprakash 这不就是他写的等价吗？间距不太理想。 - David Eisenstat

他的 so_far 部分没有说明它是区间的起点还是终点。 - cegprakash

Answer 2

注意：David Eisenstat的算法比这个更优秀。

一个简单的平面扫描算法可以在O(nlogn + m*n)时间内完成，其中m是任何单个区间与其他区间相交的最大数量。

首先对区间的端点进行排序。跟踪活动段。当到达起始点时，增加所有活动区间的相交计数，并将新区间的相交计数设置为活动区间的数量（不包括自身）。当到达结束点时，从活动区间中删除该区间。

- Sneftel

---

我不确定这是否是我们能做到的最好 - 我甚至无法想象如何进行大欧米伽分析。然而，对于稀疏分布的间隔，m 项可能会被 log n 项主导。 - Sneftel

等等，我有点傻了。稍等一下，我会发布一个更好的算法。 - Sneftel

实际上，我提出的更好算法的想法存在缺陷。是的，我认为那可能是我们能做到的最好的了。 - Sneftel

很酷。好知道。非常感谢。非常感激。如果有完美的解决方案，请告诉我。 :) - user3216886

我自己也很好奇。当这个问题有资格时，我会在上面设置赏金。 - Sneftel

Answer 3

一段关于编程的英文句子，含有HTML代码，大意为：“David方法的Python实现。”

def max_interval_count(intervals):
    interval_sorted = []
    for idx, interval in enumerate(intervals):
        s, e = interval
        interval_sorted.append([s, idx, 0]) # 0 for start
        interval_sorted.append([e, idx, 1]) # 1 for end
    interval_sorted.sort(key = lambda x: x[0])

    print(interval_sorted)

    number_of_starts = 0
    number_of_ends = 0

    overlap_count = {} 
    for event in interval_sorted:
        _, idx, start_end = event
        if start_end == 0: # start event
            # subtract all the ending before it
            overlap_count[idx] = - (number_of_ends)
            number_of_starts += 1
        else: # end event
            overlap_count[idx] += (number_of_starts - 1) # -1 as we should not include the start from the same interval
            number_of_ends += 1
    print(overlap_count)
    ans_idx = -1
    max_over_count = 0
    min_len_interval = 99999999999
    for idx, overl_cnt in overlap_count.items():
        if overl_cnt > max_over_count:
            ans_idx = idx
            max_over_count = overl_cnt
        elif overl_cnt == max_over_count and overl_cnt > 0 and (intervals[idx][1] - intervals[idx][0] + 1) < min_len_interval:
            min_len_interval = (intervals[idx][1] - intervals[idx][0] + 1)
            ans_idx = idx
    if ans_idx == -1:
        return ans_idx
    return intervals[ans_idx]


if __name__ == "__main__":
    test_1 = [[1,5],[5,10],[5,5]]
    test_2 = [[1,2],[3,5]]
    test_3 = [(1,6), (2,3), (4,11)]
    ans = max_interval_count(test_1)
    print(ans)
    print("---------")
    ans = max_interval_count(test_2)
    print(ans)
    print("---------")
    ans = max_interval_count(test_3)
    print(ans)
    print("---------")

[[1, 0, 0], [5, 0, 1], [5, 1, 0], [5, 2, 0], [5, 2, 1], [10, 1, 1]]
{0: 0, 1: 1, 2: 1}
[5, 5]
---------
[[1, 0, 0], [2, 0, 1], [3, 1, 0], [5, 1, 1]]
{0: 0, 1: 0}
-1
---------
[[1, 0, 0], [2, 1, 0], [3, 1, 1], [4, 2, 0], [6, 0, 1], [11, 2, 1]]
{0: 2, 1: 1, 2: 1}
(1, 6)
---------

- Zabir Al Nazi