题解 | #合并区间#

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类ArrayList
     * @return Interval类ArrayList
     */
  public static ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        // write code here
        intervals.sort(new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if(o1.start>o2.start){
                    return 1;
                }else if(o1.start==o2.start){
                    return o1.end-o2.end;
                }else {
                    return -1;
                }
            }
        });
        ArrayList<Interval> arrayList = new ArrayList<>();
        if(intervals.size()==0){
            return arrayList;
        }
     
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(int i=1;i<intervals.size();i++){
            if(intervals.get(i).start<=end){
                end = Math.max(intervals.get(i).end,end);
            }else if(intervals.get(i).start>end){
                arrayList.add(new Interval(start,end));
                start = intervals.get(i).start;
                end = intervals.get(i).end;
            }
        }
        arrayList.add(new Interval(start,end));
        return arrayList;
    }
}

本题考察的知识点主要是双指针的引用，所用编程语言是java.本题首先需要对intervals进行排序，每个interval按照start从小到大，start相等时按照end从小到大进行排序。排序完之后主要想清楚双指针的更新条件，双指针的更新条件如下：

if(intervals.get(i).start<=end){

end = Math.max(intervals.get(i).end,end);

}else if(intervals.get(i).start>end){

arrayList.add(new Interval(start,end));

start = intervals.get(i).start;

end = intervals.get(i).end;

}

最后， arrayList.add(new Interval(start,end))是重中之中，不然结果就少了一个interval