使用IntervalTree https://en.wikipedia.org/wiki/Interval_tree
Python中有一个可用的实现:
pip install intervaltree
import intervaltree
intervals = [
[77, 83],
[97, 103],
[76, 82],
[95, 101],
[72, 78],
[91, 97],
[66, 72],
[83, 89],
[57, 63],
[72, 78],
[47, 53],
[59, 65],
[35, 41],
[44, 50],
[22, 28],
[28, 34],
[8, 14],
[10, 16],
]
tree = intervaltree.IntervalTree.from_tuples(intervals)
print(tree)
tree.merge_overlaps()
print(tree)
tree.merge_overlaps(strict=False)
print(tree)
请注意,我必须将您的点设置为
(start, end)
而不是
(end, start)
。
IntervalTree([Interval(8, 14), Interval(10, 16), Interval(22, 28), Interval(28, 34), Interval(35, 41), Interval(44, 50), Interval(47, 53), Interval(57, 63), Interval(59, 65), Interval(66, 72), Interval(72, 78), Interval(76, 82), Interval(77, 83), Interval(83, 89), Interval(91, 97), Interval(95, 101), Interval(97, 103)])
合并到
IntervalTree([Interval(8, 16), Interval(22, 28), Interval(28, 34), Interval(35, 41), Interval(44, 53), Interval(57, 65), Interval(66, 72), Interval(72, 83), Interval(83, 89), Interval(91, 103)])
并且使用strict=False
,可以合并相邻的时间间隔
IntervalTree([Interval(8, 16), Interval(22, 34), Interval(35, 41), Interval(44, 53), Interval(57, 65), Interval(66, 89), Interval(91, 103)])
[[76, 83], ...]
?原始数据中的数对是否总是按降序排列,而你期望的结果数对是否应该按升序排列? - user2390182