一、題目描述

二、題目思路

這里提供滿足基本要求的解題思路：

1.先對列表內按照start大小升序排序，這里創建Comparator接口的實現類，重寫compare方法。

2.遍歷intervals，設置laststart、lastend兩個變量與當前區間相比較，合并公共空間，注意存在區間A包含區間B的情況。

3.在遍歷完成后，還要注意把 [laststart,lastend] 區間加到返回列表中。

三、代碼實現

import java.util.*;
/** public class Interval {*   int start;*   int end;*   public Interval(int start, int end) {*     this.start = start;*     this.end = end;*   }* }*/class CompareImpl implements Comparator<Interval> {//重寫比較方法，按照Interval.start排序，如果相等按照end排序@Overridepublic int compare(Interval inter1, Interval inter2) {if (inter1.start < inter2.start) {return -1;} else if (inter1.start == inter2.start) {if (inter1.end <= inter2.end) {return -1;} else {return 1;}} else {return 1;}}}public class Solution {/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可*** @param intervals Interval類ArrayList* @return Interval類ArrayList*/public ArrayList<Interval> merge (ArrayList<Interval> intervals) {// write code hereif (intervals.size() <= 1) {return intervals;}//首先對intervals進行排序intervals.sort(new CompareImpl());//遍歷intervals，合并公共空間ArrayList<Interval> resarr = new ArrayList<>(0);Iterator<Interval> intiv = intervals.iterator();int laststart = -1, lastend = -1;while (intiv.hasNext()) {Interval nowinterval = intiv.next();if (laststart == -1) { //當前集合不需要合并操作時laststart = nowinterval.start;lastend = nowinterval.end;} else {if (lastend >= nowinterval.start) {//這里合并時，除了 [[1,2],[2,3]] 還要注意測試用例 [[1,4],[2,3]] 的情況lastend=lastend<nowinterval.end?nowinterval.end:lastend;} else {Interval newinterval = new Interval(laststart, lastend);resarr.add(newinterval);//更新laststart和lastendlaststart=nowinterval.start;lastend=nowinterval.end;}}}//最后還需要把laststart和lastend區間加入到resarr中Interval newinterval = new Interval(laststart, lastend);resarr.add(newinterval);return resarr;}
}

四、刷題鏈接

合并區間_牛客題霸_牛客網