[LeetCode][Java] Insert Interval

题目：

?

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：

给定[1,3],[6,9]，插入并合并[2,5] 得到[1,5],[6,9].

样例2：

给定[1,2],[3,5],[6,7],[8,10],[12,16],插入并合并[4,9] 得到 [1,2],[3,10],[12,16].

这是因为新的间隔数[4,9] 覆盖了[3,5],[6,7],[8,10].

算法分析：

* 结合方法《Merge Intervals》
* 新加入 newInterval ,重新排序后然后按照上面的方法就好

AC代码：

?

public class Solution 
{
    public List
   
     insert(List
    
      intervals, Interval newInterval) { intervals.add(newInterval); if (intervals == null || intervals.size() <= 1) return intervals; return merge(intervals); } public static List
     
       merge(List
      
        intervals) { if (intervals == null || intervals.size() <= 1) return intervals; // sort intervals by using self-defined Comparator 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) { // merged case 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; } }