<p>这里有一个解决方案。它可能不是很像Python,因为我对Python的经验非常有限,但它很管用。在</p>
<pre><code>pairs_a = [(0, 5), (10, 12)]
pairs_b = [(1, 2), (11, 15)]
pairs_c = [(1, 4), (10, 12), (15, 17)]
merged = pairs_a + pairs_b + pairs_c
merged.sort()
set_list = []
cur_set = set()
cur_max = merged[0][1]
for pair in merged:
p0, p1 = pair
if cur_max < p0:
set_list.append(cur_set)
cur_set = set()
cur_set.add(p0)
cur_set.add(p1)
if cur_max < p1:
cur_max = p1
set_list.append(cur_set)
out_list = []
for my_set in set_list:
my_list = sorted(my_set)
p0 = my_list[0]
for p1 in my_list[1:]:
out_list.append((p0, p1))
p0 = p1
# more pythonic but less readable in spite of indentation efforts:
# out_list = [pair
# for zipped in [zip(list[:-1], list[1:])
# for list in [sorted(set)
# for set in set_list]]
# for pair in zipped]
# alternate ending:
# out_list = [sorted(set) for set in set_list]
print(out_list)
</code></pre>
<p>其思想是首先按第一项对所有范围对进行排序。这就是<code>merged.sort()</code>所做的(它使用连续的元组成员来消除歧义,但这在这里并不重要)。然后我们循环排序后的范围对,只要我们在一堆重叠的范围内,我们就把所有的开始和结束添加到当前集合中。为了知道束流何时结束,我们保持所有射程结束的最大值。一旦一个范围开始超过这个最大值,我们通过将当前集合附加到一个列表来存储它,并开始一个新的集合。最后一个集合必须在循环之后添加到列表中。现在我们有了一个集合列表,我们可以很容易地将其转换为列表列表或成对列表。在</p>