Insert Interval

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).Have you met this question in a real interview? YesProblem Correction

Example

Insert (2, 5) into [(1,2), (5,9)], we get [(1,9)].

Insert (3, 4) into [(1,2), (5,9)], we get [(1,2), (3,4), (5,9)].

一开始check的时候，intervals的size可以为0

只需要判断三种情况，1 是在新interval 前 切不相交，2 在新interval后不相交，3 相交。更新插入位置 只在第一种情况下更新，因为后面的 第三种情况还不确定，第二种情况肯定是插在新interval后面，所以不影响

时间复杂度：遍历一遍list o(n), list add to end. o(1)，如果list不是插入在end，就是O(n),所以最后一步插入是o(n), 最终时间复杂度是o(n)

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if(newInterval == null || intervals == null){
            return intervals;
        }
        
        List<Interval> list = new ArrayList<>();
        int insertPos = 0;
        for(Interval it : intervals){
            if(it.end < newInterval.start){
                list.add(it);
                insertPos++;
            }else if(it.start > newInterval.end){
                list.add(it);
                //insertPos++;
            }else{
                newInterval.start = Math.min(newInterval.start,it.start);
                newInterval.end = Math.max(newInterval.end, it.end);
            }
        }
        
        list.add(insertPos,newInterval);
        
        
        return list;
    }
}