题解 | #合并区间#
合并区间
https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a
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; } } }