擅长:python、mysql、java
<p>当然,如果你想的话,你可以通过强力检查所有的组合来解决这个问题。如果你需要这个算法来缩放,你可以用(伪)nlogn来实现。从技术上讲,你可以得到一个退化的最坏情况是O(n**2),但这是什么呢。在</p>
<p>基本上,你对范围进行排序,然后对于一个给定的范围,你看它的左上角的边界是否重叠,如果是这样的话,你就把重叠的间隔标记为结果。伪代码(实际上几乎是有效的python,看看这个):</p>
<pre><code>ranges.sort()
for left_range, current_range, right_range in sliding_window(ranges, 3):
if left_range.right < current_range.left:
continue
while right_range.left < min(left_range.right, current_range.right):
results.append(overlap(left_range, right_range))
right_range = right_range.next
#Before moving on to the next node, extend the current_range's right bound
#to be the longer of (left_range.right, current_range.right)
#This makes sense if you think about it.
current_range.right = max(left_range.right, current_range.right)
merge_overlapping(results)
</code></pre>
<p>(您还需要在末尾合并一些可能重叠的范围,这是另一个nlogn操作-尽管n在那里通常要小得多。我将不讨论这方面的代码,但它与上面的方法类似,涉及排序然后合并。<a href="https://stackoverflow.com/questions/5679638/merging-a-list-of-time-range-tuples-that-have-overlapping-time-ranges">See here for an example</a>。)</p>