L9: Insert Intervals | Greedy Algorithms Playlist

Welcome to the comprehensive study notes for mastering the Insert Interval problem using greedy algorithms. This guide breaks down the intuition, visual mental models, edge cases, step-by-step pseudo-code, and optimal time-space complexity analysis.

1. Problem Statement & Core Objective

We are given an array of intervals (intervals) and a single new interval (newInterval).

Input Characteristics:
- intervals is a 2D array of size $N \times 2$ where each interval has a starting point and an ending point ([start, end]).
- The input intervals array is already sorted in ascending order based on the start times.
- The input intervals array is non-overlapping by default.
The Task: Insert newInterval into intervals such that the resulting array remains sorted and completely non-overlapping. If overlapping occurs, merge the overlapping intervals into a single unified interval.

2. Core Mental Model: The Three-Segment Breakdown

To solve this efficiently, we can visualize the problem by splitting the sorted array into three distinct geographic zones relative to the newInterval:

Structure & Concept Flow

[ Left Non-Overlapping Segment ] -> [ Middle Overlapping Segment ] -> [ Right Non-Overlapping Segment ]

Left Segment: Intervals that end strictly before newInterval begins. These have no overlap and belong directly in the final output.
Middle Segment: Intervals that overlap with newInterval. These must be merged into a single consolidated interval by finding the minimum start time and maximum end time across all overlapping elements.
Right Segment: Intervals that begin strictly after newInterval ends. Since the input array is sorted, any interval starting after our new merged interval will also never overlap and can be appended directly.

3. Real-Life Analogy: Merging Calendar Events

Real-Life Analogy: Imagine scheduling meetings on a sorted office calendar wall. You want to insert a new meeting request (newInterval). Instead of rewriting the entire wall, you walk down the timeline from left to right:

You skip past all meetings that finish well before your new meeting starts (Left segment).

The moment you hit a meeting that clashes with your time slot, you rope in all subsequent overlapping meetings, taking the earliest start time and latest end time to form one big master meeting slot (Middle segment).

Once you clear the clashes, every meeting further down the calendar wall sits safely untouched (Right segment).

4. Step-by-Step Evolution & Examples

Example 1: Simple Overlap

Given Intervals: [[1, 3], [6, 9]]
New Interval: [2, 5]
Walkthrough:
- [1, 3] ends at 3, while [2, 5] starts at 2. They overlap!
- Merge them by taking the minimum start (1) and maximum end (5) -> [1, 5].
- Combine with the remaining non-overlapping interval [6, 9].
Result: [[1, 5], [6, 9]]

Example 2: Multiple Overlaps (Complex Case)

Given Intervals: [[1, 2], [3, 4], [5, 8], [6, 7], [8, 10], [12, 16]]
New Interval: [6, 8]
Segment Breakdown:
- Left Segment: [1, 2], [3, 4] (End before 6, no overlap -> Push directly to result).
- Middle Segment: [5, 8], [6, 7], [8, 10] (Overlap with [6, 8]).
  - Merge logic: Take min(starts) = 5, max(ends) = 10 -> New merged interval: [5, 10].
- Right Segment: [12, 16] (Starts after 10, no overlap -> Push directly to result).
Result: [[1, 2], [3, 4], [5, 10], [12, 16]]

5. Algorithm Design & Pseudo-Code

Here is the precise logic to implement the three-segment traversal strategy:

PYTHON

def insert(intervals, newInterval):
    res = []
    i = 0
    n = len(intervals)
    
    # Phase 1: Collect all intervals on the LEFT (no overlap)
    # Condition: current interval ends BEFORE newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        res.append(intervals[i])
        i += 1
        
    # Phase 2: Merge all overlapping intervals in the MIDDLE
    # Condition: current interval starts BEFORE or AT newInterval ends
    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
        
    # Push the fully merged newInterval into result
    res.append(newInterval)
    
    # Phase 3: Collect all remaining intervals on the RIGHT (no overlap)
    while i < n:
        res.append(intervals[i])
        i += 1
        
    return res

6. Complete Flow Walkthrough (Tracing Example 2)

Let us trace how pointers and arrays move during execution for intervals = [[1, 2], [3, 4], [5, 8], [6, 7], [8, 10], [12, 16]] and newInterval = [6, 8]:

Structure & Concept Flow

Initial State: i = 0, res = []

1. Phase 1 (Left Loop):

- i = 0 ([1, 2]): ends at 2 < newInterval start (6). True!

res.append([1, 2]) -> res = [[1, 2]], i becomes 1.

- i = 1 ([3, 4]): ends at 4 < newInterval start (6). True!

res.append([3, 4]) -> res = [[1, 2], [3, 4]], i becomes 2.

- i = 2 ([5, 8]): ends at 8 < 6 is False. Loop terminates.

2. Phase 2 (Middle Loop):

- i = 2 ([5, 8]): starts at 5 <= newInterval end (8). True!

newInterval[0] = min(6, 5) = 5

newInterval[1] = max(8, 8) = 8

i becomes 3.

- i = 3 ([6, 7]): starts at 6 <= 8. True!

newInterval[0] = min(5, 6) = 5

newInterval[1] = max(8, 7) = 8

i becomes 4.

- i = 4 ([8, 10]): starts at 8 <= 8. True!

newInterval[0] = min(5, 8) = 5

newInterval[1] = max(8, 10) = 10

i becomes 5.

- i = 5 ([12, 16]): starts at 12 <= 8 is False. Loop terminates.

- res.append([5, 10]) -> res = [[1, 2], [3, 4], [5, 10]].

3. Phase 3 (Right Loop):

- i = 5 ([12, 16]): i < n is True.

res.append([12, 16]) -> res = [[1, 2], [3, 4], [5, 10], [12, 16]], i becomes 6.

- Loop terminates (i == n).

Final Return: [[1, 2], [3, 4], [5, 10], [12, 16]]

7. Complexity Analysis

Complexity Type	Order of Growth	Rationale
Time Complexity	$\mathcal{O}(N)$	We traverse the input `intervals` array at most once across all three phases (`while` loops advance pointer `i` linearly).
Space Complexity	$\mathcal{O}(N)$	Required to store the resulting `res` list. If counting output space as mandatory, auxiliary space is $\mathcal{O}(1)$ .

8. Summary and Key Takeaways

Greedy Strategy: Break the problem down into three independent sequential phases (Left non-overlapping, Middle overlapping merge, Right non-overlapping).
Merge Rule: When intervals collide, the unified interval takes the minimum of start times and maximum of end times.
Leverage Sorted Property: Because the input array is already sorted, we do not need sorting overhead ( $\mathcal{O}(N \log N)$ ), allowing an optimal $\mathcal{O}(N)$ linear scan.
Pointer Efficiency: A single traversal index i is sufficient to navigate through all three segments cleanly without resetting or extra memory buffers.
Optimality: You cannot achieve a time complexity better than $\mathcal{O}(N)$ because every element in the array must be inspected at least once to determine its position.