Insert Interval

The problem description can be found in LeetCode.

Approach

This is a classic Interval problem.

We can divide the algorithm in three steps:

1. Add the non-overlapping intervals smaller than the new one.
2. Merge the overlapping intervals.
3. Add the remaining intervals.

Solution

from typing import List


class Solution:
    def insert(
        self, intervals: List[List[int]], newInterval: List[int]
    ) -> List[List[int]]:
        ans = []
        i = 0

        # 1.
        while i < len(intervals) and intervals[i][1] < newInterval[0]:
            ans.append(intervals[i])
            i += 1

        # 2.
        while i < len(intervals) and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        ans.append(newInterval)

        # 3.
        while i < len(intervals):
            ans.append(intervals[i])
            i += 1

        return ans

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the size of the intervals list.