LeetCode: 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].
Solution: 
Below is a simple solution in Python:

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:

    def insert(self, intervals, newInterval):
        l = []
        count = 0
        while(count < len(intervals)):
            if(newInterval.start <= intervals[count].end):
                if(newInterval.end >= intervals[count].start):
                    newInterval.start = min(intervals[count].start, newInterval.start)
                break
            l.append(intervals[count])
            count += 1
        l.append(newInterval)
        while(count < len(intervals)):
            if(newInterval.end < intervals[count].start):
                break
            l[-1].end = max(intervals[count].end, l[-1].end)
            count += 1
        while(count < len(intervals)):
            l.append(intervals[count])
            count += 1
        return l

And here is a faster solution using binary search:

class Solution:  
  
    def insert(self, intervals, newInterval):  
        if len(intervals) == 0:  
            return [newInterval]  
              
        v1 = self.search(intervals, newInterval.start,0, len(intervals)-1, 0)  
        v2 = self.search(intervals, newInterval.end,(v1)>>1, len(intervals)-1, 1)  
   
        if (v1 & 1):  
            newInterval.start = intervals[v1>>1].start   
        if (v2 & 1):  
            newInterval.end = intervals[(v2)>>1].end 
                  
        return intervals[:(v1>>1)] + [newInterval] + intervals[(v2+1)>>1:] 
          
    def search(self, intervals, index, start=0, end=0, isStart=0):  
        while(start <= end):  
            middle = (end+start)>>1 
            if intervals[middle].start <= index and intervals[middle].end >= index:  
                return (middle << 1)+1 
            if intervals[middle].start > index:  
                end = middle - 1
            else:
                start = middle + 1       
        return start << 1

Third solution:

class Solution: 
  
    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        left = [i for i in intervals if i.end < s]
        right = [i for i in intervals if i.start > e]
        if left + right != intervals:
            s = min(s, intervals[len(left)].start)
            e = max(e, intervals[~len(right)].end)
        return left + [Interval(s, e)] + right

If you want to train the code reading skills, here is another approach in Java:

/**
 * Definition for an interval.
 **/
class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
}

public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval){
        List<Interval> is = new ArrayList<Interval>();
        if(intervals == null || newInterval == null) return is;

        int status = 0;
        Interval open = null;
        for(Interval i: intervals){

            //if not found a interval containing the newInterval
            if(status==0){
                if(i.start > newInterval.end){
                    is.add(newInterval);
                    is.add(i);
                    status = 2;
                }else if(i.end < newInterval.start){
                    is.add(i);
                }else if(i.start<= newInterval.start && i.end < newInterval.end){
                    open = new Interval(i.start, newInterval.end);
                    status = 1;
                }else if(i.start > newInterval.start && i.end < newInterval.end){
                    status = 1;
                    open = new Interval(newInterval.start, newInterval.end);
                }else {
                    is.add(new Interval(Math.min(newInterval.start, i.start), i.end));
                    status = 2;
                }
            }else if(status == 1){
                if(i.start <= newInterval.end && i.end>= newInterval.end){
                    status = 2;
                    open.end = i.end;
                    is.add(open);
                }else if(i.start > newInterval.end){
                    status = 2;
                    open.end = newInterval.end;
                    is.add(open);
                    is.add(i);
                }                
            }else {   //status = 2
                is.add(i);
            }
        }

        if(status == 0) is.add(newInterval);
        if(status == 1){
            open.end = newInterval.end;
            is.add(open);
        }
        return is;
    }
}