Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
1 class intervalComparator implements Comparator<Interval>{ 2 @Override 3 public int compare(Interval o1, Interval o2) { 4 return o1.start-o2.start; 5 } 6 } 7 public class Solution { 8 public List<Interval> merge(List<Interval> intervals) { 9 List<Interval> result = new ArrayList<Interval>(); 10 if (intervals.size() == 0) { 11 return result; 12 } 13 Collections.sort(intervals, new intervalComparator()); 14 Interval first = intervals.get(0); 15 Interval next; 16 for (int i = 1; i <intervals.size() ; i++) { 17 next = intervals.get(i); 18 if (first.end < next.start) { 19 result.add(first); 20 first = next; 21 } else { 22 if (first.end < next.end) { 23 first.end = next.end; 24 } 25 } 26 } 27 result.add(first); 28 return result; 29 } 30 31 public List<Interval> insert(List<Interval> intervals, Interval newInterval) { 32 List<Interval> result = new ArrayList<Interval>(intervals); 33 result.add(newInterval); 34 return merge(result); 35 } 36 }
原文：http://www.cnblogs.com/birdhack/p/4263356.html