输入一批区间，输出合并后的区间
示例：
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
算法描述：
第一步，必须先排序，根据区间的起始start来排序。
第二部，当我们有了有序的区间集合后，就可以遍历每个区间。定义待入队的基准区间（最开始为第一个区间），并且比较目前遍历到的区间的start是否小于等于待入队基准区间end。如果是，那这两个区间可以合并了，修改基准区间的end。否则，这个待入队的基准区间可以直接加入结果队列，然后更新待入队基准区间为刚遍历的区间。
代码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();
}
});
//定义第一个合并后的区间开始
int start = intervalList.get(0).getStart();
//定义第一个合并后的区间结束
int end = intervalList.get(0).getEnd();
for(Interval i : intervalList){
//如果当前遍历到的区间start小于合并后的区间end，说明当前区间和合并后的区间存在重合
if(i.getStart() <= end){
//需要把重合的区间合并到合并后的区间中
end = Math.max(end, i.getEnd());
} else {
//else说明当前和要合并的区间没有重合,把合并后的区间加入到res中，并重置合并后的区间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 +
'}';
}
}
网友评论