题目:
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],(原始区间)
return [1,6],[8,10],[15,18].(最终区间)
思路:
该题是一道极角排序的类似题目。我们可以使用O(n)复杂度解决该题。
首先,定义二维数组Base[num][2]。以Base[i][0]记录以i为start的权值base;Base[i][1]记录以i为end的权值base;
base 的初始值为0,则遇到一个start就自增1,遇到一个end就自减1.则base从0 到正的那个点就一定是最终该区间的起点;而base从正到0的那个点,一定就是......
阅读全文