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 }