2015年9月23日星期三

Leetcode 56 Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
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;  
   }  
 }  

没有评论:

发表评论