Insert Interval

Problem

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.

Example 1:

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

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],[8,10].

Constraints:

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

Solution

Approach: Three-Part Merge

The key insight is to divide intervals into three parts: before newInterval, overlapping with newInterval, and after newInterval.

Implementation

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

        # Add all intervals that come before newInterval
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        # Merge all overlapping intervals with newInterval
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1

        result.append(newInterval)

        # Add all remaining intervals
        while i < n:
            result.append(intervals[i])
            i += 1

        return result

Approach 2: Single Pass

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

        for interval in intervals:
            # newInterval comes before current interval
            if newInterval[1] < interval[0]:
                result.append(newInterval)
                newInterval = interval
            # Current interval comes before newInterval
            elif interval[1] < newInterval[0]:
                result.append(interval)
            # Overlapping - merge
            else:
                newInterval[0] = min(newInterval[0], interval[0])
                newInterval[1] = max(newInterval[1], interval[1])

        result.append(newInterval)
        return result

Complexity Analysis

Time Complexity: O(n), where n is the number of intervals. Single pass through intervals.
Space Complexity: O(1), not counting output array. We only use constant extra space.

Key Insights

Sorted Input: Input intervals are already sorted, making the problem easier.
Three Phases:
- Phase 1: Intervals completely before newInterval
- Phase 2: Intervals overlapping with newInterval (merge them)
- Phase 3: Intervals completely after newInterval
Overlap Condition: Two intervals [a, b] and [c, d] overlap if a <= d and c <= b, or equivalently max(a,c) <= min(b,d).
Merge Strategy: When merging, take minimum of starts and maximum of ends.
No Sorting Needed: Since input is sorted, we don’t need to sort the output.
Edge Cases: Handle empty intervals array, newInterval before all intervals, newInterval after all intervals.