For example,
Given
return
Given
[1,3],[2,6],[8,10],[15,18]
,return
[1,6],[8,10],[15,18]
.
Solution 1: Use compactor interface to sort with start. if next interval is not overlap then just add to result otherwise update the end value use max of current end and next end.
public class Solution {
class IntervalCompare implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
return a.start-b.start;
}
}
public List<Interval> merge(List<Interval> intervals) {
IntervalCompare iComp=new IntervalCompare();
Collections.sort(intervals,iComp);
List<Interval> res=new ArrayList<>();
for (Interval x: intervals) {
int n=res.size();
if (n==0 || res.get(n-1).end<x.start) res.add(x);
else if (res.get(n-1).end<x.end) res.get(n-1).end=x.end;
}
return res;
}
}
没有评论:
发表评论