Merge Intervals leetcode

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].

 讲解转自http://codeganker.blogspot.com/2014/03/merge-intervals-leetcode.html

"这是一道关于interval数组结构的操作，在面试中也是一种比较常见的数据结构。假设这些interval是有序的（也就是说先按起始点排序，然后如果起始点相同就按结束点排序），那么要把它们合并就只需要按顺序读过来，如果当前一个和结果集中最后一个有重叠，那么就把结果集中最后一个元素设为当前元素的结束点（不用改变起始点因为起始点有序，因为结果集中最后一个元素起始点已经比当前元素小了）。那么剩下的问题就是如何给interval排序，在java实现中就是要给interval自定义一个Comparator，规则是按起始点排序，然后如果起始点相同就按结束点排序。整个算法是先排序，然后再做一次线性遍历，时间复杂度是O(nlogn+n)=O(nlogn)，空间复杂度是O(1)，因为不需要额外空间，只有结果集的空间。"

Comparable 和Comparator用法

Comparable

一个实现了comparable接口的对象的实例可以被用于和相同对象的不同实例做对比。它本身必须实现java.lang.Comparable的接口，这样它就拥有了对比的能力。

有一部分类实现了Comparable接口,如Integer Double和String等。 
Comparable接口有一个comparTo(Object o)方法,它返回整数类型。java.lang.Comparable: int compareTo(Object o1)

这个方法用于当前对象与o1对象做对比，返回int值，分别的意思是：

• positive – 当前对象大于o1
• zero – 当前对象等于o1
• negative – 当前对象小于o1

Comparator

一个实现了comparator接口的对象能够对比不同的对象。它不能用于同一个类的不同实例的对比，但是可以用于其他的类的实例做对比。它必须实现java.util.Comparator的接口。

java.util.Comparator: int compare(Object o1, Objecto2)

这个方法用于o1与o2对象做对比，返回int值，分别的意思是：

• positive – o1大于o2
• zero – o1等于o2
• negative – o1小于o2



java.util.Collections.sort(List) 和 java.util.Arrays.sort(Object[]) 方法被用来排列使用内在排序（natural ordering）方式的对象
java.util.Collections.sort(List, Comparator) 和 java.util.Arrays.sort(Object[], Comparator)方法在Comparator如果可供比较的时候会被用到。
综上, 如果有comparable接口的排序就用Colletions.sort(list), 没有救用Colletion.sort(list, comparator)
所以这里要写一个comparator

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }
        ArrayList<Interval> res = new ArrayList<Interval>();
        Comparator<Interval> com= new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        };
        Collections.sort(intervals, com);
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (prev.end >= cur.start) {
                prev = new Interval(prev.start, Math.max(prev.end, cur.end));
            } else {
                res.add(prev);
                prev = cur;
            }
        }
        res.add(prev);//把最后一个prev添加到结果里
        return res;
    }

}