python - 寻找一种按休息时间分割类次的算法

Question

我有一个由整数开始时间和结束时间定义的轮类列表，例如

shifts = [[0,10], [12,18], [22,37]]

我还有一个以相同方式定义的中断列表:

breaks = [[2,3], [5,8], [22,25]]

我正在寻找一种算法，可以在发生中断的地方拆分类次:

def split_shifts(shifts, breaks):
    # missing code

对于上面的例子，函数返回

split_shifts(shifts, breaks)
> [[0,2],[3,5],[8,10],[12,18],[25,37]]

我的方法是

new_shifts = []
for pause in breaks:
    for shift in shifts:
        if time_overlap(shift, pause):
            new_shifts.extend(split_shift(shift, pause))
            break

但结果是错误的，其中多个中断与同一个类次重叠。

你会如何解决这个问题？看起来我需要在更改 new_shifts 的元素时循环 new_shifts。

Answer 1

您可以对两个嵌套列表进行展平、连接和排序，然后将元素两两配对，同时消除成对的相同元素。

flat = sorted(sum(shifts, []) + sum(breaks, []))
[[flat[idx], flat[idx+1]] for idx in range(0, len(flat)-1, 2) if flat[idx] != flat[idx+1]]

输出:

[[0, 2], [3, 5], [8, 10], [12, 18], [25, 37]]