BM89 题解 | #合并区间#

官方题解：贪心 + 双指针

1. 重写一个Collections.sort() 方法，按照区间开头start进行升序排序
2. 使用一个结果集res，以及res的指针count，用于指明操作的是哪个区间（一般是最后一个）
3. 开始遍历，新遍历到的区间有两种情况：
1. 新区间的start <= 原区间的end：说明有重叠的，把当前res中count指向的区间的end修改为 max(新.end, 旧.end)
2. 新区间的start > 原区间的end：说明肯定没有重叠，后续也不会有区间来和当前的原区间重叠，因为区间是按照start升序排列的，后续的区间的start只会比当前新区间的start大。所以原区间就可以“归档”到结果集中了。res.add(新区间); count++;
4. 最后返回res即可

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) {
        ArrayList<Interval> res = new ArrayList<>();
        if (intervals.size() == 0) return res;
        if (intervals.size() == 1) return intervals;

        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval o1, Interval o2) {
                // 升序，小的放在前面
                if (o1.start != o2.start) {
                    return o1.start - o2.start;
                } else {
                    return o1.end - o2.end;
                }
            }
        });

        // 初始化区间，把第一个区间放进res
        res.add(intervals.get(0));
        // res中的区间指针，表示当前是在处理第几个区间
        int count = 0;
        // 遍历后续区间
        for (int i = 1; i < intervals.size(); ++i) {
            // 拿到当前遍历到的区间
            Interval ii = intervals.get(i);
            // 拿到当前操作的区间
            Interval origin = res.get(count);
            if (ii.start > origin.end) { 
                // 旧origin已经不会再有重叠了。（ii开头比origin结尾都大，后续的区间开头更大）
                res.add(ii);        // 把ii作为第二个区间加入结果集res
                count++;            // count++，接下来就要对这个新来的orgin进行操作了
            }
            if (ii.start <= origin.end) {    // 说明有重叠
                origin.end = Math.max(origin.end, ii.end);
            }
        }

        return res;
    }
}