Insert Interval

Problem: Insert Interval

The general idea to solve this problem is first to check where the start of the new interval should locate, and then to check where the end of the new interval should locate. For the boundary, there can be situations that start or end of new interval lies inside an interval or between intervals. For former situation, we can substitute start of the new interval by start of overlapping interval, or vice versa for end of interval. For the latter situation, we simply insert head or end of new interval. We only need to care about what happens at the boundaries of new interval. For what's in its range, we can just ignore then since they will definitely merged into the new interval.

Code in Python:

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        for i, interval in enumerate(intervals):
            if newInterval.start <= interval.end:
                if interval.start <= newInterval.start:
                    newInterval.start = interval.start
                insert_start = i
                break
        else:
            insert_start = len(intervals)

        for i, interval in enumerate(itertools.islice(intervals, insert_start, None), insert_start):
            if newInterval.end <= interval.end:
                if interval.start <= newInterval.end:
                    newInterval.end = interval.end
                    insert_end = i + 1
                else:
                    insert_end = i
                break
        else:
            insert_end = len(intervals) + 1

        intervals[insert_start:insert_end] = [newInterval]
        return intervals