题解 | #合并区间#

package com.hhdd.双指针;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * 做不出来
 *
 * @Author huanghedidi
 * @Date 2022/8/7 17:43
 */
public class 合并区间 {


    public static ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        if (intervals.size() == 0) {
            return intervals;
        }

        // 先按照start进行排序
        intervals.sort(new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });

        ArrayList<Interval> res = new ArrayList<>();
        // 将第一个区间先放入
        Interval interval = intervals.get(0);
        res.add(new Interval(interval.start, interval.end));
        int cur = 0;
        for (int i = 1; i < intervals.size(); i++) {
            Interval tmp = intervals.get(i);
            if (tmp.start <= res.get(cur).end) {
                // 说明有交集
                if (tmp.end <= res.get(cur).end) {
                    // 说明完全包含，直接跳过
                    continue;
                } else {
                    // 更新结果的结束边界
                    res.get(cur).end = tmp.end;
                }
            } else {
                // 说明无交集 断开的区间
                cur++;
                res.add(new Interval(tmp.start, tmp.end));
            }
        }
        return res;
    }


    static class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }
}