合并一组具有重叠时间范围的时间区间元组列表

Question

我有一个元组列表，其中每个元组都是 (开始时间，结束时间)。我正在尝试合并所有重叠的时间范围，并返回一个不同时间范围的列表。

例如:

[(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的方式来实现相同的目标？

感谢您的帮助。谢谢！

- Praveen Gollakota

Answer 1

一些使其更高效、更符合Python风格的方法:

1. 消除set()构造，因为算法应该在主循环中消除重复项。
2. 如果只需要迭代结果，请使用yield生成值。
3. 减少中间对象的构造，例如:将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))

- samplebias

Answer 2

对元组进行排序，若 t1.right>=t2.left => 合并并用新列表重新开始，...

-->

def f(l, sort = True):
    if sort:
        sl = sorted(tuple(sorted(i)) for i in l)
    else:
        sl = l
    if len(sl) > 1:
        if sl[0][1] >= sl[1][0]:
            sl[0] = (sl[0][0], sl[1][1])
            del sl[1]
            if len(sl) < len(l):
                return f(sl, False)
    return sl

- manji

---

如果在开头存在无法合并的范围，例如[(6,11), (13, 40), (33, 44)]，则此算法无法工作。 - Gabriel

Answer 3

晚了一些，但可能有助于寻找这个问题的人。我遇到了类似的问题，但是涉及到字典。给定一组时间范围，我想要查找重叠部分，并在可能时将它们合并。对@samplebias答案进行了一点修改，我得到了以下结果： 合并函数：

def merge_range(ranges: list, start_key: str, end_key: str):
    ranges = sorted(ranges, key=lambda x: x[start_key])
    saved = dict(ranges[0])

    for range_set in sorted(ranges, key=lambda x: x[start_key]):
        if range_set[start_key] <= saved[end_key]:
            saved[end_key] = max(saved[end_key], range_set[end_key])
        else:
            yield dict(saved)
            saved[start_key] = range_set[start_key]
            saved[end_key] = range_set[end_key]
    yield dict(saved)

数据：

data = [
    {'start_time': '09:00:00', 'end_time': '11:30:00'},
    {'start_time': '15:00:00', 'end_time': '15:30:00'},
    {'start_time': '11:00:00', 'end_time': '14:30:00'},
    {'start_time': '09:30:00', 'end_time': '14:00:00'}
]

Execution:

print(list(merge_range(ranges=data, start_key='start_time', end_key='end_time')))

输出：

[
    {'start_time': '09:00:00', 'end_time': '14:30:00'},
    {'start_time': '15:00:00', 'end_time': '15:30:00'}
]

- Nirmal

Answer 4

排序部分：使用标准排序，它已经以正确的方式比较元组。

sorted_tuples = sorted(initial_ranges)

合并部分。它还可以消除重复的范围，因此不需要一个set。假设您有current_tuple和next_tuple。

c_start, c_end = current_tuple
n_start, n_end = next_tuple
if n_start <= c_end: 
  merged_tuple = min(c_start, n_start), max(c_end, n_end)

我希望逻辑足够清晰。

要查看下一个元组，您可以使用索引访问已排序的元组；它是一个完全已知的序列。

- 9000

Answer 5

将所有边界排序，然后取所有满足一个边界的结束是另一个边界的开始的边界对。

def mergeOverlapping(initialranges):
    def allBoundaries():
        for r in initialranges:
            yield r[0], True
            yield r[1], False

    def getBoundaries(boundaries):
        yield boundaries[0][0]
        for i in range(1, len(boundaries) - 1):
            if not boundaries[i][1] and boundaries[i + 1][1]:
                yield boundaries[i][0]
                yield boundaries[i + 1][0]
        yield boundaries[-1][0]

    return getBoundaries(sorted(allBoundaries()))

哼，虽然不太美观但至少写起来很有趣！

编辑：多年后，受到了一次点赞之后，我意识到我的代码错了！这是新版本，只是为了好玩：

def mergeOverlapping(initialRanges):
    def allBoundaries():
        for r in initialRanges:
            yield r[0], -1
            yield r[1], 1

    def getBoundaries(boundaries):
        openrange = 0
        for value, boundary in boundaries:
            if not openrange:
                yield value
            openrange += boundary
            if not openrange:
                yield value

    def outputAsRanges(b):
        while b:
            yield (b.next(), b.next())

    return outputAsRanges(getBoundaries(sorted(allBoundaries())))

基本上，我用-1或1标记边界，然后按值对它们进行排序，并且只有在开放括号和关闭括号之间的平衡为零时才输出它们。

- UncleZeiv

Answer 6

当使用Python 3.7时，遵循“每次尝试运行应用程序时都会引发StopIteration错误”的建议，@UncleZeiv的outputAsRanges方法应该是：

    def outputAsRanges(b):
        while b:
            try:
                yield (next(b), next(b))
            except StopIteration:
                return

- cesc