Solution: Insert Interval

Statement

You are given a list of non-overlapping intervals, intervals, where each interval is represented as [starti, endi] and the list is sorted in ascending order by the start of each interval (starti). You are also given another interval, newInterval = [start, end].

Your task is to insert newInterval into the list of intervals such that the list remains sorted by starting times and still contains no overlapping intervalsOverlapping intervals are two or more intervals with at least one common point in time.. If any intervals overlap after the insertion, merge them accordingly.

Return the updated list of intervals.

Note: You don’t need to modify intervals in place. You can make a new array and return it.

Constraints:

• $0 \leq$ intervals.length $\leq 10^4$

• intervals[i].length, newInterval.length $== 2$

• $0 \leq$ starti $<$ endi $\leq 10^4$

• The list of intervals is sorted in ascending order based on the start time.

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach involves iterating through the list of intervals and checking for overlaps with a new interval. If overlap occurs, the new interval merges with the existing one. After iterating the entire list, if no overlap occurs, append the new interval. Finally, we sort the list based on the start times of the intervals to ensure the correct order of intervals.

Iterating through the intervals to merge or append the new interval based on overlaps takes $O(n)$ time, where $n$ represents the number of intervals. Then, sorting the output list takes $O(n \log n)$ time. Therefore, the overall time complexity of this solution is $O(n \log n)$ due to sorting being the dominant factor. 

Optimized approach using the merge intervals pattern

The optimized approach avoids unnecessary sorting by leveraging the fact that the input list is already sorted and non-overlapping. We traverse the list once: first, we copy all intervals that end before the new interval starts — these cannot overlap and are added directly to the result. Next, we check for an overlap between the new interval and the last interval added. If there is no overlap, we simply append the new interval. Otherwise, we merge them by updating the end boundary to the maximum of the two. We then continue scanning the remaining intervals: if an interval does not overlap with the last one in the result, it is appended as is; if it overlaps, we merge it by updating the end boundary. This approach performs all operations in a single linear pass, resulting in an efficient $O(n)$ time complexity, which is a significant improvement over the naive solution that requires sorting.