擅长:python、mysql、java
<p>您可以使用对分模块获得O(NlogN)解决方案,而无需实际排序:</p>
<pre><code>lst = [[1, 4], [17, 20], [2, 3], [16, 18], [6, 6], [6, 7], [9, 13], [21, 24]]
from bisect import bisect_left
starts = [] # merged starting values
ends = [] # merged ending values
for (start,end) in lst:
iLeft = bisect_left(ends,start-1) # first position after start
iRight = bisect_left(starts,end+1) # first position after end
starts[iLeft:iRight] = [min([start]+starts[iLeft:iLeft+1])] # insert/merge
ends[iLeft:iRight] = [max([end]+ends[iRight-1:iRight])]
merged = list(zip(starts,ends)) # combine starts and ends
print(merged)
[(1, 4), (6, 7), (9, 13), (16, 24)]
</code></pre>