MANG Problem #33: Insert Interval (Hard)

1. 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).

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

2. Approach: Linear Scan & Merge

Since the list is already sorted, we can do this in exactly one pass ($O(n)$) without sorting again.

1. Left Disjoint: All intervals ending before newInterval starts are added to the result.
2. Overlap: All intervals that overlap with newInterval are merged by updating the boundaries of newInterval (start = min(starts), end = max(ends)).
3. Right Disjoint: All intervals starting after the merged newInterval ends are added to the result.

3. Java Implementation

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0, n = intervals.length;

    // 1. Add all intervals that end before newInterval starts
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.add(intervals[i]);
        i++;
    }

    // 2. Merge overlapping intervals
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.add(newInterval); // Add the merged interval

    // 3. Add all remaining intervals
    while (i < n) {
        result.add(intervals[i]);
        i++;
    }

    return result.toArray(new int[result.size()][]);
}

4. 5-Minute "Video-Style" Walkthrough

1. The "Aha!" Moment: Because the array is sorted, the intervals fall into three distinct buckets: strictly before, overlapping, and strictly after.
2. The Overlap Condition: An interval overlaps if its start is $\le$ the new interval's end. (Since we already skipped those that end before it starts).
3. The Merge: We don't add the overlapping intervals to the list. Instead, we expand our newInterval to "swallow" them. We only add newInterval to the result list once the overlap phase is completely over.

5. Interview Discussion

• Interviewer: "What is the time complexity?"
• You: "O(N), because we scan through the intervals exactly once."
• Interviewer: "What if the original list was not sorted?"
• You: "Then we would have to append the new interval and run the standard $O(N \log N)$ Merge Intervals algorithm."