删除重叠区间并分成非重叠区间 Python

Question

我有一个排序的区间列表List1： [1,10], [2,4], [6,8], [20,30], [24,28], [35,40], [45,50]

我知道重叠间隔是List2：[2,4], [6,8], [24,28]

我想从中获取非重叠间隔，这样输出就是：[1,2], [4,6], [8,10], [20,24], [28,30], [35,40], [45,50]

我怎样才能在 Python 中有效地做到这一点？

我的第一个想法是，我应该为 List2 中遇到的每个重叠区间创建一个新的区间列表 List1，并删除 List2 的相应元素（继续这个直到 List2 为空），但我一直在让它工作时遇到一些麻烦。这在本质上似乎与许多区间问题不同，所以任何建议都会很棒！

Answer 1

我不知道这是否是最有效的方法，但这对您来说可能是一个很好的起点：

data = [[1, 10], [2, 4], [6, 8], [20, 30], [24, 28], [35, 40], [45, 50]]
flat_data = sorted([x for sublist in data for x in sublist])
new_intevals = [flat_data[i:i + 2] for i in range(0, len(flat_data), 2)]

print(new_intevals)
# output: [[1, 2], [4, 6], [8, 10], [20, 24], [28, 30], [35, 40], [45, 50]]

删除重叠区间并分成非重叠区间 Python

Remove Overlapping Intervals & Divide into Non-overlapping Intervals Python

python

intervals

overlapping