Level:
Medium
题目描述:
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
思路分析:
定义一个数据类型interval
public class Interval{
int start; //序列对的首元素
int end;//序列对的尾元素
public Interval(int s,int e){
start=s;
end=e;
}
}
将题目给出的所有序列对的首元素都保存在一个数组starts,将所有尾元素保存在另外一个数组ends,然后将两个数组排序,设置两个指针,i 和 j。从头开始遍历数组,如果starts[i+1]>ends[i],那么产生一个以ends[i]作为尾部的Interval,头部为starts[j],j的初始值是0,随后每产生一个Interval,j 就更新为(i+1);当i==n-1时,也会产生一个最后一个Interval。
代码:
/**
* 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; }
* }
*/
public class Solution{
public List<Interval>merge(List<Interval>intervals){
List<Interval>finalList=new AarryList<>();
int []starts=new int[intervals.size()];
int []ends=new int[intervals.size()];
for(int i=0;i<intervals.size();i++){
starts[i]=intervals.get(i).start;
ends[i]=intervals.get(i).end;
}
Arrays.sort(starts);
Arrays.sort(end);
for(int i=0,j=0;i<starts.length;i++){
if(i==n-1||starts[i+1]>ends[i]){
Interval interval=new Interval(starts[j],ends[i]);
finalList.add(interval);
j=i+1;
}
}
return finalList;
}
}