NC37 合并区间 算法java实现
程序员文章站
2024-03-16 13:21:40
...
题目描述
给出一组区间,请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
示例1
输入:
[[10,30],[20,60],[80,100],[150,180]]
返回值:[[10,60],[80,100],[150,180]]
解题思路
判断两个区间是否重叠,就是看一个区间的开始是不是小于另外一个区间的结束,也就是a.end>b.begin,然后由于本题的区间没有顺序,这对我们依次合并会产生干扰,因此我们需要排序,因此需先对其排序,在这里使用区间的begin进行排序,排完序后使用两个指针指向相邻区间进行比较,如果符合条件则合并,继续往后移动找下一个合并对象,直到没得合并,就把当前合并后的值加入结果列表中,直到最后一个元素遍历完为止。
代码实现
import java.util.*;
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
[[10,30],[20,60],[80,100],[40,180]]
[[10,70],[40,60],[80,100],[150,180]]
[[10,30],[40,60],[30,40]]
[[10]]
[[]]
* }
*/
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
//1、先对数组列表进行排序
//2、遍历列表
//3、从第二个元素开始,如果与上个元素有重叠,则合并元素(所谓的合并是将起始值变成两个元素中的最小最大值),如果没有则继续
Collections.sort(intervals,new Comparator<Interval>(){
public int compare(Interval o1,Interval o2){
if(o1.start>o2.start){
return 1;
}else{
return -1;
}
}
});
ArrayList<Interval> list = new ArrayList<>();
int curent=0;
int end=intervals.size();
int next=1;
while(next<=end){
if(next<end&&intervals.get(curent).end>=intervals.get(next).start){
intervals.get(curent).start=Math.min(intervals.get(curent).start,intervals.get(next).start);
intervals.get(curent).end=Math.max(intervals.get(curent).end,intervals.get(next).end);
}else{
list.add(intervals.get(curent));
curent=next;
}
next++;
}
return list;
}
}
上一篇: Androidstudio报错记录
下一篇: ffmpeg 多张图片转视频