盗号网站怎么做/无锡seo网站管理

给出若干闭合区间，合并所有重叠的部分。
样例
给出的区间列表 => 合并后的区间列表：
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]
挑战
O(n log n) 的时间和 O(1) 的额外空间。

一刷ac
解题思路：按照start进行快排，然后每次比较start和end的关系，用来进行合并。

/*** Definition of Interval:* public class Interval {*     int start, end;*     Interval(int start, int end) {*         this.start = start;*         this.end = end;*     }*/class Solution {/*** @param intervals, a collection of intervals* @return: A new sorted interval list.*/public List<Interval> merge(List<Interval> intervals) {List<Interval> res = new ArrayList<Interval>();if(intervals == null || intervals.size() == 0) return res;quicksort(intervals, 0, intervals.size()-1);int start = intervals.get(0).start;int end = intervals.get(0).end;for(int i = 1; i < intervals.size(); i++){if(end < intervals.get(i).start){Interval tmp = new Interval(start, end);res.add(tmp);start = intervals.get(i).start;end = intervals.get(i).end;} else{end = Math.max(end, intervals.get(i).end);}}Interval tmp = new Interval(start, end);res.add(tmp);return res;}public void quicksort(List<Interval> intervals, int low, int high){if(low > high) return;int left = low;int right = high;int mid = (left + right) / 2;int pivot = intervals.get(mid).start;while(left <= right){while(intervals.get(left).start < pivot) left++;while(intervals.get(right).start > pivot) right--;if(left <= right){Interval tmpleft = intervals.get(left);Interval tmpright = intervals.get(right);intervals.set(left, tmpright);intervals.set(right, tmpleft);left++;right--;}}if(left < high) quicksort(intervals, left, high);if(right > low) quicksort(intervals, low, right);}}