php 合并区间段,区间合并算法

输入一批区间，输出合并后的区间

示例：

输入: [[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 intervals = new ArrayList<>();

intervals.add(interval1);

intervals.add(interval2);

List res = merge(intervals);

res.forEach(p->System.out.println(p));

}

public static List merge(List intervalList){

List res = new ArrayList<>();

Collections.sort(intervalList, new Comparator() {

@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 +

'}';

}

}