Problem Statement in English

You’re given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the i-th interval and intervals is sorted in ascending order by start_i.

You’re also given an interval newInterval = [start, end] that represents the start and end of another interval.

Return intervals after inserting newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Approach

This is a one line difference compared to the solution in post 56. Merge Intervals.

We just need to append the new interval to the list of intervals and then call the merge function. Tada!

And we’re done!

Solution in Python


class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        def merge():
            res = []
            intervals.sort()
            buffer = [intervals[0][0], intervals[0][1]]

            for start, stop in intervals:
                if buffer[1] < start:
                    res.append(buffer.copy())
                    buffer[0], buffer[1] = start, stop
                elif buffer[1] < stop:
                    buffer[1] = stop
                
            res.append(buffer)

            return res

        intervals.append(newInterval)
        return merge()

Complexity

  • Time: $O(n \log n)$
    Since we are sorting the intervals, the time complexity is dominated by the sorting step, which takes $O(n \log n)$ time, where $n$ is the number of intervals.

  • Space: $O(1)$
    Since we are modifying the intervals in place and using a constant amount of extra space for the buffer and result list, the space complexity is $O(1)$.

And we are done.