Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

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

Return intervals after the insertion.

Additional information

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^5
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 10^5

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

Output: [[1,5],[6,9]]

Explanation: The new interval [2,5] overlaps with [1,3], merging them into [1,5]. The interval [6,9] remains unchanged.

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

Output: [[1,2],[3,10],[12,16]]

Explanation: Because the new interval [4,8] overlaps with [3,5], [6,7], and [8,10].

Brute Force (Insert and Sort)

Intuition

A very straightforward way to solve this is to completely ignore the fact that the input array is already sorted.

We can simply append the newInterval to the end of the intervals array. Once it is added, we re-sort the entire array based on the starting values of each interval. After the array is sorted, this problem becomes identical to the classic "Merge Intervals" problem! We iterate through the sorted list, and whenever an interval's start time is less than or equal to the previous interval's end time, we merge them by taking the maximum of their end times.

Algorithm

1. Append newInterval to the intervals list.
2. Sort the intervals list based on the 0th index (the start time) of each interval.
3. Initialize an empty merged list.
4. Iterate through each interval in the sorted intervals list:

• If merged is empty, or if the current interval's start time is strictly greater than the last merged interval's end time (merged[-1][1] < interval[0]), there is no overlap. Append the current interval to merged.
• Otherwise, there is an overlap! Update the end time of the last interval in merged to be the maximum of its current end time and the new interval's end time.

5. Return the merged list.

def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    # Append the new interval and sort the entire list
    intervals.append(new_interval)
    intervals.sort(key=lambda x: x[0])
    
    merged = []
    
    # Standard interval merging logic
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
            
    return merged

Time & Space Complexity

• Time complexity: O(N log N)

• Reason: N is the total number of intervals. Appending the interval takes O(1) time, but sorting the entire list takes O(N log N) time. The subsequent merge pass takes O(N) time. Overall time is strictly dominated by the sorting step.

• Space complexity: O(N)

• Reason: We create a new merged list that can hold up to N elements.

Linear Single-Pass Merge - Optimal

Intuition

Because the input intervals array is already sorted, sorting it again is a massive waste of time. We can achieve the exact same result in a single pass!

As we iterate through the intervals, we compare the current interval with our newInterval. There are only exactly three possible scenarios:

1. The new interval comes before the current interval: If the newInterval ends before the current interval even starts, we know we have completely bypassed any potential overlaps. We can safely append the newInterval to our result, followed by all remaining intervals!
2. The new interval comes after the current interval: If the newInterval starts after the current interval ends, there is no overlap yet. We just append the current interval to our result and keep searching.
3. There is an overlap! If neither of the above is true, the intervals must be colliding. We merge them by updating our newInterval's start time to the minimum of both starts, and its end time to the maximum of both ends. We do not append it to the result yet, because this newly expanded newInterval might overlap with the next interval in the array!

Algorithm

1. Initialize an empty res list to store the final intervals.
2. Iterate i from 0 to the length of intervals minus 1:

• Case 1 (No overlap, new interval is first): If newInterval[1] < intervals[i][0], append newInterval to res. Since all subsequent intervals are guaranteed to be strictly greater, immediately return res + intervals[i:].
• Case 2 (No overlap, current interval is first): If newInterval[0] > intervals[i][1], append intervals[i] to res.
• Case 3 (Overlap): Update newInterval to be [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])].

3. If the loop finishes without triggering Case 1, it means the newInterval (which may have merged with several other intervals) belongs at the very end of the list. Append newInterval to res.
4. Return res.

def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    res = []
    
    for i in range(len(intervals)):
        # Case 1: new_interval is completely before the current interval
        if new_interval[1] < intervals[i][0]:
            res.append(new_interval)
            return res + intervals[i:]
            
        # Case 2: new_interval is completely after the current interval
        elif new_interval[0] > intervals[i][1]:
            res.append(intervals[i])
            
        # Case 3: Intervals overlap, so we merge them
        else:
            new_interval = [
                min(new_interval[0], intervals[i][0]),
                max(new_interval[1], intervals[i][1])
            ]
            
    # If the loop finishes, the merged new_interval goes at the very end
    res.append(new_interval)
    return res

Time & Space Complexity

• Time complexity: O(N)

• Reason: We iterate through the intervals array at most exactly one time. Appending to the list and slicing the remainder takes linear time.

• Space complexity: O(N)

• Reason: We create a new res array to store the merged intervals, which will contain up to N elements.