python - 合并具有重叠时间范围的时间范围元组的列表

我有一个元组列表，其中每个元组都是(start-time, end-time)。我正在尝试合并所有重叠的时间范围，并返回不同时间范围的列表。
例如

[(1, 5), (2, 4), (3, 6)] --->  [(1,6)]
[(1, 3), (2, 4), (5, 8)] --->  [(1, 4), (5,8)]

这是我的实现方法。

# Algorithm
# initialranges: [(a,b), (c,d), (e,f), ...]
# First we sort each tuple then whole list.
# This will ensure that a<b, c<d, e<f ... and a < c < e ...
# BUT the order of b, d, f ... is still random
# Now we have only 3 possibilities
#================================================
# b<c<d: a-------b           Ans: [(a,b),(c,d)]
#                  c---d
# c<=b<d: a-------b          Ans: [(a,d)]
#               c---d
# c<d<b: a-------b           Ans: [(a,b)]
#         c---d
#================================================
def mergeoverlapping(initialranges):
    i = sorted(set([tuple(sorted(x)) for x in initialranges]))

    # initialize final ranges to [(a,b)]
    f = [i[0]]
    for c, d in i[1:]:
        a, b = f[-1]
        if c<=b<d:
            f[-1] = a, d
        elif b<c<d:
            f.append((c,d))
        else:
            # else case included for clarity. Since
            # we already sorted the tuples and the list
            # only remaining possibility is c<d<b
            # in which case we can silently pass
            pass
    return f

我想弄清楚是否

是某些python模块中的内置函数，可以更有效地执行此操作吗？或

是否有实现相同目标的更多Python方式？

感谢您的帮助。谢谢!

最佳答案

使用Pythonic可以提高效率的几种方法:

消除了set()的构造，因为该算法应在主循环中删除重复项。

如果只需要遍历结果，请使用yield生成值。

减少中间对象的构造，例如:将tuple()调用移至产生最终值的位置，从而省去了构造和丢弃多余元组的麻烦，并重用了saved列表来存储当前时间范围以进行比较。

代码:

def merge(times):
    saved = list(times[0])
    for st, en in sorted([sorted(t) for t in times]):
        if st <= saved[1]:
            saved[1] = max(saved[1], en)
        else:
            yield tuple(saved)
            saved[0] = st
            saved[1] = en
    yield tuple(saved)

data = [
    [(1, 5), (2, 4), (3, 6)],
    [(1, 3), (2, 4), (5, 8)]
    ]

for times in data:
    print list(merge(times))

关于python - 合并具有重叠时间范围的时间范围元组的列表，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5679638/