輸入一批區(qū)間，輸出合并后的區(qū)間
示例：
輸入: [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6]
算法描述：
? ?第一步猛计，必須先排序唠摹，根據(jù)區(qū)間的起始start來(lái)排序。
? ?第二部奉瘤，當(dāng)我們有了有序的區(qū)間集合后勾拉，就可以遍歷每個(gè)區(qū)間。定義待入隊(duì)的基準(zhǔn)區(qū)間（最開(kāi)始為第一個(gè)區(qū)間）毛好，并且比較目前遍歷到的區(qū)間的start是否小于等于待入隊(duì)基準(zhǔn)區(qū)間end望艺。如果是，那這兩個(gè)區(qū)間可以合并了肌访，修改基準(zhǔn)區(qū)間的end找默。否則，這個(gè)待入隊(duì)的基準(zhǔn)區(qū)間可以直接加入結(jié)果隊(duì)列吼驶，然后更新待入隊(duì)基準(zhǔn)區(qū)間為剛遍歷的區(qū)間惩激。
代碼demo：
/**
* 2019/5/6 下午5:45
*
* @author Jungler
* @since
*/
public class Solution {
public static void main(String[] args) {
Interval interval1 = new Interval(1,3);
Interval interval2 = new Interval(2,4);
List<Interval> intervals = new ArrayList<>();
intervals.add(interval1);
intervals.add(interval2);
List<Interval> res = merge(intervals);
res.forEach(p->System.out.println(p));
}
public static List<Interval> merge(List<Interval> intervalList){
List<Interval> res = new ArrayList<>();
Collections.sort(intervalList, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.getStart() - o2.getStart();
}
});
//定義第一個(gè)合并后的區(qū)間開(kāi)始
int start = intervalList.get(0).getStart();
//定義第一個(gè)合并后的區(qū)間結(jié)束
int end = intervalList.get(0).getEnd();
for(Interval i : intervalList){
//如果當(dāng)前遍歷到的區(qū)間start小于合并后的區(qū)間end，說(shuō)明當(dāng)前區(qū)間和合并后的區(qū)間存在重合
if(i.getStart() <= end){
//需要把重合的區(qū)間合并到合并后的區(qū)間中
end = Math.max(end, i.getEnd());
} else {
//else說(shuō)明當(dāng)前和要合并的區(qū)間沒(méi)有重合,把合并后的區(qū)間加入到res中蟹演，并重置合并后的區(qū)間start和end
res.add(new Interval(start, end));
start = i.getStart();
end = i.getEnd();
}
}
res.add(new Interval(start, end));
return res;
}
}
class Interval{
private int start;
private int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public int getStart() {
return start;
}
public void setStart(int start) {
this.start = start;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
@Override
public String toString() {
return "Interval{" +
"start=" + start +
", end=" + end +
'}';
}
}
