题解 | 合并区间

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 ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        // write code here
        ArrayList<Interval> res = new ArrayList<>();
        ArrayList<int[]> events = new ArrayList<>();
        for (Interval cur : intervals) {
            events.add(new int[] {cur.start, -1}); //开始事件
            events.add(new int[] {cur.end, 1}); //结束事件
        }
        Collections.sort(events, (a, b)-> {
            if (a[0] != b[0])return a[0] - b[0];
            else return a[1] - b[1]; //相同时间开始事件在前
        });
        int count = 0;
        int curStartTime = 0;
        for (int[] eve : events) {
            if (eve[1] == -1) {
                if (count == 0) curStartTime = eve[0];
                count++;
            } else {
                count--;
                if (count == 0) {
                    res.add(new Interval(curStartTime, eve[0]));
                }
            }
        }
        return res;
    }
    public ArrayList<Interval> merge2 (ArrayList<Interval> intervals) {
        // write code here
        Collections.sort(intervals, (a, b)->a.start - b.start);
        ArrayList<Interval> res = new ArrayList<>();
        for (Interval cur : intervals) {
            if (res.isEmpty() || res.get(res.size() - 1).end < cur.start) {
                res.add(new Interval(cur.start, cur.end));
            } else {
                // 合并区间，更新 end
                Interval last = res.get(res.size() - 1);
                last.end = Math.max(last.end, cur.end);
            }
        }

        return res;
    }
}