1. Append newInterval to the existing list of intervals.
2. Sort the entire list based on start times.
3. Iterate through the sorted list and merge adjacent intervals if they overlap.

Pseudo-code:

text
function bruteForce(intervals, newInterval):
    intervals.append(newInterval)
    intervals.sort(by start time)
    
    result = []
    for interval in intervals:
        if result is empty or result.last.end < interval.start:
            result.add(interval)
        else:
            result.last.end = max(result.last.end, interval.end)
    return result

Complexity Analysis: The time complexity is dominated by the sorting step, which is $O(N \log N)$. While this produces the correct answer, it is inefficient. The problem constraints state that the input intervals are already sorted. By re-sorting, we fail to utilize the most critical property of the input data, leading to suboptimal performance.

Core Insight for Insert Interval

The key intuition for the LeetCode 57 Solution lies in the sorted nature of the input. Because the intervals are ordered by start time, we can process the data linearly from left to right.

We can visualize the existing intervals as blocks on a timeline. The newInterval is a block we are trying to drop in. This naturally divides the problem into three distinct phases:

1. Non-overlapping Left: Intervals that end before the newInterval starts. These are unaffected and can be added directly to the result.
2. Overlapping Middle: Intervals that intersect with newInterval. We must merge all of these into a single "super-interval." The start of this new interval is the minimum of all involved start times, and the end is the maximum of all involved end times.
3. Non-overlapping Right: Intervals that start after the newInterval ends. These are also unaffected and can be added directly.

Visual Description: Imagine iterating through the list with a pointer. First, we skip past all intervals completely to the left of our target. Once we hit an interval that touches our target, we enter a "merge mode." We expand our target interval to engulf every subsequent interval it touches. Once we encounter an interval that starts strictly after our expanded target ends, we exit "merge mode," add the finalized target to our result, and copy the remaining intervals as is.

Execution Flow

Let's trace the algorithm with intervals = [[1,3], [6,9]] and newInterval = [2,5].

1. Initialization: i = 0, n = 2, result = [].
2. Phase 1 (Left Check):
   • Check intervals[0] ([1,3]). Does it end before newInterval starts (3 < 2)? No.
   • Phase 1 loop ends immediately.
3. Phase 2 (Merge Check):
   • Check intervals[0] ([1,3]). Does it start before newInterval ends (1 <= 5)? Yes.
   • Merge: newInterval becomes [min(1,2), max(3,5)] -> [1,5]. Increment i to 1.
   • Check intervals[1] ([6,9]). Does it start before newInterval ends (6 <= 5)? No.
   • Phase 2 loop ends.
4. Add Step: Add the updated newInterval ([1,5]) to result. result is now [[1,5]].
5. Phase 3 (Right Check):
   • Check intervals[1] ([6,9]). It is remaining. Add to result.
   • result is now [[1,5], [6,9]]. Increment i to 2.
   • i equals n, loop ends.
6. Return: [[1,5], [6,9]].

Proof of Correctness

The correctness relies on the sorted invariant and the transitive property of overlaps.

1. Order Preservation: By processing left-to-right, we ensure that the intervals added in Phase 1 appear before the merged interval, and those in Phase 3 appear after. Since the input is sorted, the output remains sorted.
2. Overlap Resolution: The greedy choice in Phase 2 captures all intervals that intersect the newInterval. By taking the minimum start and maximum end, we guarantee the resulting interval covers the entire continuous range of the union.
3. Disjointness:
   • Phase 1 intervals end before newInterval starts (by definition).
   • Phase 3 intervals start after newInterval ends (by definition, as Phase 2 consumes everything else).
   • Therefore, no overlaps exist between the three groups.

Reference Implementation

C++ Solution for LeetCode 57

cpp
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int i = 0;
        int n = intervals.size();

        // Phase 1: Add all intervals ending before newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.push_back(intervals[i]);
            i++;
        }

        // Phase 2: Merge overlapping intervals
        // While the current interval starts before (or at) the newInterval ends
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.push_back(newInterval);

        // Phase 3: Add remaining intervals
        while (i < n) {
            result.push_back(intervals[i]);
            i++;
        }

        return result;
    }
};

Java Solution for LeetCode 57

java
import java.util.ArrayList;
import java.util.List;

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

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

        // Phase 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);

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

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

Python Solution for LeetCode 57

python
class Solution:
    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
        result = []
        i = 0
        n = len(intervals)
        
        # Phase 1: Add all intervals ending before newInterval starts
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
            
        # Phase 2: Merge overlapping intervals
        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)
        
        # Phase 3: Add remaining intervals
        while i < n:
            result.append(intervals[i])
            i += 1
            
        return result

Q: Why is my output incorrect for adjacent intervals like [1,2] and [3,4]? Mistake: Confusing strict inequality < with inclusive inequality <=. Why: In interval problems, [1,2] and [2,3] usually overlap (or touch) at 2. However, the problem logic defines overlap specifically. For merging, if interval[i].end < newInterval.start, they do NOT overlap. If interval[i].start <= newInterval.end, they DO overlap. Consequence: Failing to merge intervals that touch at the boundaries.

Q: Why does my code crash with Index Out of Bounds? Mistake: Forgetting to check i < n in the while loops. Why: If newInterval is larger than all existing intervals, the loop will try to access an index that doesn't exist. Consequence: Runtime error.