合并具有重叠时间范围的时间范围元组列表 [英] Merging a list of time-range tuples that have overlapping time-ranges

问题描述

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

I have a list of tuples where each tuple is a (start-time, end-time). I am trying to merge all overlapping time ranges and return a list of distinct time ranges. For example

[(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

我想知道是否

1. 某个python模块中的内置函数是否可以更有效地执行此操作?或
2. 是否有更 Pythonic 的方式来实现相同的目标?

感谢您的帮助.谢谢！

推荐答案

一些提高效率的方法，Pythonic:

A few ways to make it more efficient, Pythonic:

1. 消除 set() 构造，因为该算法应该在主循环中删除重复项.
2. 如果您只需要迭代结果，请使用 yield 生成值.
3. 减少中间对象的构建，例如:将 tuple() 调用移动到生成最终值的位置，从而使您不必构建和丢弃额外的元组，并重用list saved 用于存储当前时间范围进行比较.

1. Eliminate the set() construction, since the algorithm should prune out duplicates during in the main loop.
2. If you just need to iterate over the results, use yield to generate the values.
3. Reduce construction of intermediate objects, for example: move the tuple() call to the point where the final values are produced, saving you from having to construct and throw away extra tuples, and reuse a list saved for storing the current time range for comparison.

代码:

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

这篇关于合并具有重叠时间范围的时间范围元组列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！