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

问题描述

我有一个元组列表，每个元组是（开始时间，结束时间）。我想合并所有重叠的时间段和返回不同的时间范围的列表。 例如

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

下面是我是如何实现它。

Here is how I implemented it.

# 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

我试图找出是否

I am trying to figure out if

1. 是一个在某些Python模块的内置功能，可以更有效地做到这一点？或
2. 是否有实现相同目标的更Python的方法？

您的帮助是AP preciated。谢谢！

Your help is appreciated. Thanks!

推荐答案

一些方法，使之更加高效，Python化：

A few ways to make it more efficient, Pythonic:

1. 消除设置（）结构中，由于算法应在主回路修剪掉重复。
2. 如果你只需要遍历结果，使用收益率生成的值。
3. 降低建筑中间对象，例如：移动元组（）打电话到最终值的生成点，让您从此不必构造，扔掉额外的元组和重用一个List 保存存储当前时间段进行比较。

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.

code：

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屋！