Insert Interval

LeetCode 57: Insert Interval Solution & Explanation

Problem Overview

TL;DR: The optimal solution iterates through the sorted intervals linearly, separating them into three groups: those strictly before the new interval, those overlapping (which are merged), and those strictly after.

In LeetCode 57, we are provided with a list of non-overlapping intervals sorted by their start time. We must insert a newInterval into this list. If the insertion creates overlaps, we must merge the overlapping intervals into a single continuous range. The final list must remain sorted and non-overlapping.

This is a classic Insert Interval problem that tests your ability to manipulate array indices and handle edge cases in geometry or scheduling contexts. It is a popular interview question because it requires recognizing that the sorted input allows for an $O(N)$ solution rather than a naive sorting approach.

Brute Force Approach for Insert Interval

A naive or brute force approach treats the problem as a generic "merge intervals" task, ignoring the fact that the original list is already sorted.

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:

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.

Algorithm Strategy: Greedy Patterns

To implement the Greedy strategy efficiently, we maintain an index i to iterate through the input intervals array and a result list (or vector) to store the output.

1. Phase 1 (Left): Iterate while the current interval's end time is strictly less than the newInterval's start time. Add these intervals to result as they are valid and untouched.
2. Phase 2 (Merge): Iterate while the current interval's start time is less than or equal to newInterval's end time. This condition identifies overlaps. For every overlapping interval, update newInterval to cover the combined range:
   • newInterval.start = min(newInterval.start, currentInterval.start)
   • newInterval.end = max(newInterval.end, currentInterval.end)
   • Do not add to result yet; we keep merging until no overlaps remain.
3. Add Merged Interval: Push the fully merged newInterval to result.
4. Phase 3 (Right): Iterate through the remaining intervals. Since the list is sorted, these are guaranteed to be to the right of the merged interval and non-overlapping. Add them to result.

This approach ensures strict $O(N)$ time complexity as each element is processed exactly once.

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.

Pattern Reuse Notes

The Greedy - Interval Merging pattern used in LeetCode 57 is highly transferable. Understanding how to process sorted segments linearly is key to solving these related problems:

• LeetCode 56: Merge Intervals: Very similar, but you must sort the input first. The "merge" logic is identical to Phase 2.
• LeetCode 759: Employee Free Time: Requires merging intervals from multiple employees to find gaps (the inverse of merging).
• LeetCode 986: Interval List Intersections: Instead of merging, you find the commonality (AND operation) between two sorted lists of intervals.
• LeetCode 2406: Divide Intervals Into Minimum Number of Groups: Uses the same interval logic but often requires a heap or sweep-line approach to count overlaps.

Reference Implementation

C++ Solution for LeetCode 57

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
9        vector<vector<int>> result;
10        int i = 0;
11        int n = intervals.size();
12
13        // Phase 1: Add all intervals ending before newInterval starts
14        while (i < n && intervals[i][1] < newInterval[0]) {
15            result.push_back(intervals[i]);
16            i++;
17        }
18
19        // Phase 2: Merge overlapping intervals
20        // While the current interval starts before (or at) the newInterval ends
21        while (i < n && intervals[i][0] <= newInterval[1]) {
22            newInterval[0] = min(newInterval[0], intervals[i][0]);
23            newInterval[1] = max(newInterval[1], intervals[i][1]);
24            i++;
25        }
26        result.push_back(newInterval);
27
28        // Phase 3: Add remaining intervals
29        while (i < n) {
30            result.push_back(intervals[i]);
31            i++;
32        }
33
34        return result;
35    }
36};

Java Solution for LeetCode 57

1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    public int[][] insert(int[][] intervals, int[] newInterval) {
6        List<int[]> result = new ArrayList<>();
7        int i = 0;
8        int n = intervals.length;
9
10        // Phase 1: Add all intervals ending before newInterval starts
11        while (i < n && intervals[i][1] < newInterval[0]) {
12            result.add(intervals[i]);
13            i++;
14        }
15
16        // Phase 2: Merge overlapping intervals
17        while (i < n && intervals[i][0] <= newInterval[1]) {
18            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
19            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
20            i++;
21        }
22        result.add(newInterval);
23
24        // Phase 3: Add remaining intervals
25        while (i < n) {
26            result.add(intervals[i]);
27            i++;
28        }
29
30        return result.toArray(new int[result.size()][]);
31    }
32}

Python Solution for LeetCode 57

1class Solution:
2    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
3        result = []
4        i = 0
5        n = len(intervals)
6        
7        # Phase 1: Add all intervals ending before newInterval starts
8        while i < n and intervals[i][1] < newInterval[0]:
9            result.append(intervals[i])
10            i += 1
11            
12        # Phase 2: Merge overlapping intervals
13        while i < n and intervals[i][0] <= newInterval[1]:
14            newInterval[0] = min(newInterval[0], intervals[i][0])
15            newInterval[1] = max(newInterval[1], intervals[i][1])
16            i += 1
17        result.append(newInterval)
18        
19        # Phase 3: Add remaining intervals
20        while i < n:
21            result.append(intervals[i])
22            i += 1
23            
24        return result