高效识别.python中类型列表中的非重叠区间

Question

我正在Python中处理元组列表，其中每个元组包含两个代表间隔起点和终点的整数。我正在尝试找出一种方法来有效地识别此列表中的非重叠间隔。 我当前的方法涉及嵌套循环来将每个间隔与每个其他间隔进行比较，效率不高，尤其是当列表很大时。

任何人都可以向我指出可以帮助我解决此问题的相关算法或库的方向吗？ :) 谢谢你！

Answer 1

对每个间隔的起点和终点进行排序，其中每个端点都与一个间隔 ID 相关联（例如列表中间隔的索引，或者任何对其存储方式有意义的内容）。

现在解析已排序的点数组，维护一组当前活动的点，最初为空。当您遇到起点时，将关联的间隔添加到您的集合中，并将其与集合中已有的所有其他内容相关联。当遇到终点时，将其从集合中删除。

完成后，所有重叠间隔都在关联对中，因此不关联的对是您的非重叠间隔。

例如

0 [1,5]
1 [3,7]
2 [6,9]

sorted array of points associated with intevals: [1=>0, 3=>1, 5=>0, 6=>2, 7=>1, 9=>2]

parse point 1: set = {0}, pairs = {}
parse point 3: set = {0,1}, pairs = {(0,1}}
parse point 5: set = {1}, pairs = {(0,1)}
parse point 6: set = {1,2}, pairs = {(0,1), (1,2)}
parse point 7: set = {2}, pairs = {(0,1), (1,2)}
parse point 9: set = {}, pairs = {(0,1), (1,2)}

间隔 0 和 1 重叠，间隔 1 和 2 也重叠，所以唯一不重叠的是 0 和 2。