algorithm - 重叠次数最少的区间

Question

我有一系列区间。我想找到重叠次数最少的区间。

例如:
输入:

[(1.1, 10.1), (2.1,10.1), (3.1, 10.1)]

因为(1.1, 2.1)重叠1次，(2.1, 3,1)重叠2次，(3.1, 10.1)重叠3次。返回 (1.1, 2.1)

我的解决方案:

1.创建一个 dict(name f_int) 来保存输入中的所有数字。{0:1.1, 1.2.1, 2:3.1 ...}

2.创建一个长度为2*len(f_int)-1的列表名称直方图，所有项均为0。奇数索引表示其两个相邻元素的“间隔”。

3.遍历输入，f_int[each.start]和f_int[each.end] += 1之间的所有项

4.在索引为奇数的直方图中求最小值，其相邻的两个元素就是结果

可以，但是当f_int很大时，速度很慢(在3中花费很多时间)

def find_least_overlap(intervals):
    all_nums = sorted([p for interval in intervals for p in interval])

    # 1
    f_int = {}
    int_f = {}
    i = 0
    for n in all_nums:
        try:
            f_int[n]
        except:
            f_int[n] = i
            int_f[i] = n
            i += 1
    # 2
    histogram = [0 for i in range(2*i-1)]

    # 3
    for interval in intervals:
        for _ in range(2*f_int[interval[0]], 2*f_int[interval[1]]+1):
            histogram[_] += 1
    # 4
    aim = [histogram[i] for i in range(len(histogram)-1) if i % 2 == 1]
    min_overlap = aim.index(min(aim)) * 2 + 1
    pre_item = (min_overlap - 1) / 2
    next_item = (min_overlap + 1) / 2
    return int_f[pre_item], int_f[next_item]

Answer 1

创建对列表 (时间，标志 = +-1 用于间隔的开始或结束)

按时间排序列表。
在平局的情况下，还要考虑开始/结束标志(如果 [1,4] 和 [4,7] 之类的间隔不应相交，则在开始之前结束，给出零长度相交范围)

使overlapping = 0

遍历列表，为每一对添加标记到overlapping

当 overlapping 改变时——输出范围结束，新的范围开始

比较overlapping与当前最小值(不包括从0开始)