2014年4月16日 星期三

[LeetCode] Merge Intervals

Problem:
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:O(n logn)
public class Solution {
   public ArrayList merge(ArrayList intervals) {
      if (intervals == null || intervals.size() <= 1)
         return intervals;
       Collections.sort(intervals, new IntervalComparator());
       ArrayList result = new ArrayList();
       Interval prev = intervals.get(0);
       for (int i = 1; i < intervals.size(); i++) {
          Interval curr = intervals.get(i);
             if (prev.end >= curr.start) {
          Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
   prev = merged;
      } else {
   result.add(prev);
   prev = curr;
      }
 }
 
 result.add(prev);
        return result;
   }
}
 
class IntervalComparator implements Comparator {
 public int compare(Interval i1, Interval i2) {
  return i1.start - i2.start;
 }
}

沒有留言:

張貼留言