题解 | #合并区间#

import java.util.*;


//  public class Interval {
//      int start;
//      int end;
//      Interval() { start = 0; end = 0; }
//      Interval(int s, int e) { start = s; end = e; }
//  }

public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        //特殊情况
        if (intervals.size() == 1){
            return intervals;
        }
        //先按照开始时间排序
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        //left为开始时间所处的时间段
        //right同一时间段可能的结束时间所处的时间段
        int left = 0;
        int right = 1;
        ArrayList<Interval> ans = new ArrayList<>();
        while (right <= intervals.size()){
        	
            while (right <= intervals.size() - 1 
            && intervals.get(left).end >= intervals.get(right).start){
            
            	if (intervals.get(left).end < intervals.get(right).end) {
                    intervals.get(left).end = intervals.get(right).end;
                }
                right++;
            }
            
            ans.add(intervals.get(left));
            left = right;
            right++;
        }
        return ans;
    }
}