题解 | #合并区间#

思路：先按区间左边界按升序排序，用Collections.sort();
1.设置双指针，一个指向当前已合并过的末尾的区间p，一个指向还未合并过的第一个区间q。
2.比较q的start值与p的end值的大小
1）若q.start<=p.end,取p.end与q.end的最大值赋给p.end，并删除q。删除后就相当于进行了q++,因此不需要额外的q++了。
2）若q.start>p.end,说明不重合。p++,q++。

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        Collections.sort(intervals,new Comparator<Interval>(){
            @Override
            public int compare(Interval o1,Interval o2){
                return o1.start-o2.start;
            }
        });
        int p=0;
        int q=1;
        while(q<intervals.size()){
            Interval ip=intervals.get(p);
            Interval iq=intervals.get(q);
            if(iq.start<=ip.end){
                ip.end=Math.max(iq.end,ip.end);
                intervals.remove(q);
            }else{
                p++;
                q++;
            }
        }
        return intervals;
    }