1、給定一組區間，表示為[start,end]，請給出方法，將有重疊的區間進行合并。例如：
給定：[1,3],[2,6],[8,10],[15,18],
合并：[1,6],[8,10],[15,18].
分析：題目很直觀，首先把區間遞增排序，然后從頭合并，合并時觀察當前區間的start是否小于或等于前一個區間的end。代碼如下：
1 public class MergeIntervals {
2 public class IntervalCmp implements Comparator<Interval> {
3 @Override
4 public int compare(Interval i1, Interval i2) {
5 if (i1.start < i2.start) return -1;
6 if (i1.start == i2.start && i1.end <= i2.end) return -1;
7 return 1;
8 }
9 }
10
11 public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
12 ArrayList<Interval> ret = new ArrayList<Interval>();
13 if (intervals.size() == 0) return ret;
14 Interval[] arr = new Interval[intervals.size()];
15 intervals.toArray(arr);
16 Arrays.sort(arr, new IntervalCmp());
17 int start = arr[0].start;
18 int end = arr[0].end;
19 for (int i = 0; i < arr.length; i++) {
20 if (arr[i].start <= end) {
21 end = Math.max(end, arr[i].end);
22 } else {
23 ret.add(new Interval(start, end));
24 start = arr[i].start;
25 end = arr[i].end;
26 }
27 }
28 ret.add(new Interval(start, end));
29 return ret;
30 }
31 }
2、給定的一組區間，將區間中的存在的任意區間的父區間刪除，例如：
給定：[1,2] [1,3] [1,4] [5,9] [6,8]
刪除后：[1,2] [6,8]
分析：此題暴力的解法的復雜度為O(N^2)。受上一題排序的啟發，是否有好一點的思路呢？
我們可以按照start遞增排序，若start相等，則按照end遞減排序。考慮排序后的第i-1 和第i個區間，由于start是遞增的，所以第i-1個區間的start肯定小于等于第i個區間的start。若第i-1個區間的end大于等于第i個區間的end，則第i-1個區間就成為第i個區間的父區間了。
按照這個思路，可以試著在排序之后逆向順序處理每一個區間。假設當前處理第i個區間，如前所述，若第i-1個區間的end大于等于第i個區間的end，則第i-1個區間成為第i個區間的父區間，可以保留第i個區間，將第i-1個區間刪除。由于第i-1個區間是第i個區間的父區間，所以第i-1個區間的父區間也是第i個區間的父區間，這種情形下刪掉第i-1個區間，后續不會漏刪第i-1個區間的父區間。若第i-1個區間的end小于第i個區間的end，則可以跳過第i個區間，開始處理第i-1個區間。因為按照這種處理的方法，在處理到第i個區間時，該區間不會是任何區間的父區間（若是父區間已經被如前所述的方法刪除了）。而且，在這種情形下，后續可能出現的第i個區間的父區間會是第i-1個區間的父區間，所以也不會漏掉第i個區間的父區間。所以排序之后逆向處理，只需要O(N)的時間，就可以解決這道問題。整體的時間復雜度為O(nlogn)。
1 public class Solution {
2 public class IntervalCmp implements Comparator<Interval> {
3 @Override
4 public int compare(Interval i1, Interval i2) {
5 if (i1.start < i2.start) return -1;
6 if (i1.start == i2.start && i1.end >= i2.end) return -1;
7 return 1;
8 }
9 }
10
11 public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
12 ArrayList<Interval> ret = new ArrayList<Interval>();
13 if (intervals.size() == 0) return ret;
14 Interval[] arr = new Interval[intervals.size()];
15 intervals.toArray(arr);
16 Arrays.sort(arr, new IntervalCmp());
17 int start = arr[arr.length - 1].start;
18 int end = arr[arr.length - 1].end;
19 for (int i = arr.length - 2; i >= 0; i--) {
20 if (arr[i].end < end) {
21 ret.add(new Interval(start, end));
22 start = arr[i].start;
23 end = arr[i].end;
24 }
25 }
26 ret.add(new Interval(start, end));
27 return ret;
28 }
29 }