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].

https://oj.leetcode.com/problems/insert-interval/

思路1：建立新的结果返回，遍历原来的线段组（注意原来是按照start排序之后的），所以根据是否和新的interval重叠，加入新的结果中（结果也要求按start排序）。

public class Solution {    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {        if (newInterval == null)            return intervals;        ArrayList<Interval> res = new ArrayList<Interval>();        for (Interval each : intervals) {            if (each.end < newInterval.start)                res.add(each);            else if (each.start > newInterval.end) {                res.add(newInterval);                newInterval = each;            } else {                newInterval = new Interval(Math.min(each.start, newInterval.start), Math.max(each.end, newInterval.end));            }        }        res.add(newInterval);        return res;    }    public static void main(String[] args) {        // Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as        Interval one = new Interval(1, 2);        Interval two = new Interval(3, 5);        Interval three = new Interval(6, 7);        Interval four = new Interval(8, 10);        Interval five = new Interval(12, 16);        ArrayList<Interval> intervals = new ArrayList<Interval>();        intervals.add(one);        intervals.add(two);        intervals.add(three);        intervals.add(four);        intervals.add(five);        System.out.println(new Solution().insert(intervals, new Interval(4, 9)));    }}

参考：

http://www.programcreek.com/2012/12/leetcode-insert-interval/

http://www.cnblogs.com/TenosDoIt/p/3715013.html