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

class Solution(object):
    def find_start(self, intervals, start):
        """
        find the index of first interval iv that iv.end >= newInterval.start
        """
        lo, hi = 0, len(intervals) - 1
        ret = -1
        while lo <= hi:
            mid = (lo+hi)/2
            iv = intervals[mid]
            if iv.end < start: lo = mid+1
            else: hi = mid-1
        return lo

    def find_end(self, intervals, end):
        """
        find the first index that doesn't overlap with new interval end point
        """
        lo, hi = 0, len(intervals) - 1
        ret = -1
        while lo <= hi:
            mid = (lo+hi)/2
            iv = intervals[mid]
            if iv.start <= end: lo = mid+1
            else: hi = mid-1
        return lo

    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        if not intervals: return [newInterval]
        first = self.find_start(intervals, newInterval.start)
        last = self.find_end(intervals, newInterval.end)

        if first == last:
            intervals.insert(first, newInterval)
        else:
            intervals[first].start = min(intervals[first].start, newInterval.start)
            intervals[first].end = max(intervals[last-1].end, newInterval.end)
            intervals[first+1:last] = []
        return intervals