给定一组区间，找出交叉点数最大的区间

Question

给定一组区间，找到交叉点最多的区间（不是特定交叉点的长度）。所以如果输入（1,6) (2,3) (4,11), (1,6)应该返回。有人建议使用Interval Tree在O（nlogn）中完成此操作，但我在阅读了它的wiki页面后不明白如何构建和使用Interval Tree。我相信可以通过某种排序和扫描算法来完成。如果Interval tree是唯一的选择，请教我如何构建/使用它。谢谢。

Answer 1

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)
---------

Answer 2

注意：David Eisenstat的算法比这个性能更好。

一个简单的平面扫描算法将在O（nlognm*n）中做到这一点，其中m是任何单个间隔的最大交叉点数。

对间隔endpoint排序。跟踪活动段。到达起点时，增加所有活动间隔的交点计数，并将新间隔的交点计数设置为活动间隔数（不包括其本身）。到达终点时，从活动间隔中删除间隔。

Answer 3

不要使用间隔树。为每个间隔endpoint创建一个事件，以便每个间隔都有一个开始事件和一个停止事件。按顺序处理这些事件。（如果测量零交点计为交点，则订单在停止之前开始，否则订单在开始之前停止。）

初始化从间隔到数字的映射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）；如果只能通过相当标准的计算几何技术添加和比较endpoint，则运行时间是最佳的。