← ~/lc-grind/posts

#56 - Merge Intervals

June 13, 2025

Merge Intervals

Problem Description

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:


Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:


Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

Solution

1. Problem Deconstruction

Technical Definition:
Given a set ( I = { [a_i, b_i] \mid 1 \leq i \leq n } ) of intervals where ( a_i \leq b_i ), merge all pairs ( [a_i, b_i] ), ( [a_j, b_j] ) satisfying ( \max(a_i, a_j) \leq \min(b_i, b_j) ). Return a minimal set ( M ) of non-overlapping intervals such that ( \bigcup_{[a,b] \in I} [a,b] = \bigcup_{[c,d] \in M} [c,d] ).

Beginner Explanation:
You have a list of time periods (e.g., meetings [1pm-3pm], [2pm-4pm]). When periods overlap (e.g., 2pm is in both [1pm-3pm] and [2pm-4pm]), combine them into a single period ([1pm-4pm]). Repeat until no more periods overlap. Return the final list.

Mathematical Formulation:
Let ( I ) be the input set. Define an equivalence relation ( \sim ) where ( [a_i, b_i] \sim [a_j, b_j] ) if ( \exists ) a sequence ( [x_0, y_0], [x_1, y_1], \dots, [x_k, y_k] ) such that:

  • ( [x_0, y_0] = [a_i, b_i] )
  • ( [x_k, y_k] = [a_j, b_j] )
  • ( \forall m \in [1, k], \max(x_{m-1}, x_m) \leq \min(y_{m-1}, y_m) )
    The output is ( { [\min_{[a,b] \in C} a, \max_{[a,b] \in C} b] \mid C \text{ is an equivalence class of } \sim } ).

Constraint Analysis:

  • ( 1 \leq n \leq 10^4 ):
    • Eliminates ( O(n^2) ) brute-force (100M operations borderline in Python).
    • Implies need for ( O(n \log n) ) or better.
  • Fixed interval length 2:
    • No variable-length handling needed.
  • ( 0 \leq a_i \leq b_i \leq 10^4 ):
    • Values fit in 16-bit integers.
    • Edge: Single-point intervals ([x, x]), nested intervals (([1,10]) contains ([2,3])), adjacent intervals (([1,4]), ([4,5])).

2. Intuition Scaffolding

Real-World Metaphor:
Like merging contiguous time blocks in a calendar. If “Team Meeting” (1pm-3pm) and “Client Call” (2pm-4pm) overlap, they become a single “Busy” block (1pm-4pm).

Gaming Analogy:
In tower defense, merging overlapping attack ranges of towers. If Tower A covers [10, 50] and Tower B covers [40, 70], their combined coverage is [10, 70].

Math Analogy:
Computing the convex hull of 1D intervals. The “hull” of overlapping intervals ( [a,b] ) and ( [c,d] ) is ( [\min(a,c), \max(b,d)] ).

Common Pitfalls:

  1. Chain Overlaps Missed: ([1,5]), ([3,7]), ([6,10]) → must merge all three.
  2. Unsorted Input Assumption: Processing in given order fails for ([[2,5], [1,3]]).
  3. Adjacency ≠ Overlap: ([1,2]), ([3,4]) don’t merge, but ([1,3]), ([3,4]) do.
  4. Inclusive/Exclusive Confusion: Endpoints are inclusive (overlap if ( a_j \leq b_i ) and ( a_i \leq b_j )).
  5. State Reset Timing: Forgetting to add the last merged interval after the loop.

3. Approach Encyclopedia

Brute Force (Multi-pass Merge)

while changed:
    changed = False
    for i in range(len(intervals)):
        for j in range(i+1, len(intervals)):
            if intervals[i] overlaps intervals[j]:
                merge intervals[i] and intervals[j]
                remove intervals[j]
                changed = True
                break
        if changed: break
  • Complexity: Worst-case ( O(n^3) ) (after ( n ) removals, each taking ( O(n^2) )).
  • Visualization:
    Initial: [[1,3],[2,6],[8,10]]  
Pass 1: Merge [1,3] & [2,6] → [[1,6],[8,10]]  
Pass 2: No merge → done

Optimal (Sort + Linear Scan)

sort intervals by start
merged = []
start, end = intervals[0]
for each [a,b] in intervals[1:]:
    if a <= end: 
        end = max(end, b)  # Extend current interval
    else:
        merged.append([start, end])  # Finalize current
        start, end = a, b  # Start new interval
merged.append([start, end])  # Add last interval
  • Complexity:
    • Time: ( O(n \log n) ) (sorting) + ( O(n) ) (scan) = ( O(n \log n) ).
    • Space: ( O(1) ) extra (excluding output).
  • Visualization:
    Sorted: [[1,3], [2,6], [8,10]]
Step 1: [1,3] → current=[1,3]
Step 2: [2,6] → 2<=3 → current=[1,6]
Step 3: [8,10] → 8>6 → append [1,6], start [8,10]
Output: [[1,6], [8,10]]

Line Sweep (Event-Based)

events = []
for [a,b] in intervals:
    events.append((a, "start"))
    events.append((b, "end"))
sort events by position, "start" before "end"
count = 0, current_start = None
for (pos, type) in events:
    if type == "start":
        count += 1
        if count == 1: current_start = pos
    else:
        count -= 1
        if count == 0: 
            merged.append([current_start, pos])
  • Complexity: ( O(n \log n) ) (sorting 2n events).
  • Visualization:
    [[1,3],[2,6]] → events: (1,start), (3,end), (2,start), (6,end)
Sorted: (1,start), (2,start), (3,end), (6,end)
At 1: count=1 → current_start=1
At 2: count=2
At 3: count=1
At 6: count=0 → append [1,6]

4. Code Deep Dive

def merge(intervals):
    if not intervals:  # Handle empty input
        return []
    intervals.sort(key=lambda x: x[0])  # Sort by start
    merged = []
    start, end = intervals[0]  # Initialize first interval
    for i in range(1, len(intervals)):
        a, b = intervals[i]
        if a <= end:  # Overlap condition
            end = max(end, b)  # Merge by extending end
        else:
            merged.append([start, end])  # Finalize non-overlapping
            start, end = a, b  # Reset to current
    merged.append([start, end])  # Add last interval
    return merged

Edge Case Handling:

  • Example 1 ([[1,3],[2,6]]):
    • Line 7: a=2 <= end=3 → end = max(3,6)=6.
    • Final merged.append([1,6]).
  • Example 2 ([[1,4],[4,5]]):
    • Line 7: a=4 <= end=4 → end = max(4,5)=5.
    • Output [[1,5]].
  • Disjoint Intervals ([[1,2],[3,4]]):
    • Line 7: 3 > 2 → append [1,2], then [3,4].

5. Complexity War Room

Hardware-Aware Analysis:

  • 10,000 intervals → Sorting: ( \approx 133k ) ops (Python Timsort), Scan: 10k ops.
  • Memory: 20k integers (160KB), fits in L3 cache (4-50MB).

Approach Comparison:

Method Time Space Readability Interview Viability
Brute Force ( O(n^3) ) ( O(1) ) 7/10 ❌ (Fails >100)
Sort + Scan ( O(n \log n) ) ( O(n) ) 10/10 ✅ (Optimal)
Line Sweep ( O(n \log n) ) ( O(n) ) 6/10 ⚠ (Overkill)

6. Pro Mode Extras

Variants:

  1. Insert Interval (LC 57):
    def insert(intervals, new):
     merged = []
     for i, interval in enumerate(intervals):
         if new[1] < interval[0]:  # No overlap, insert before
             return merged + [new] + intervals[i:]
         elif new[0] > interval[1]:  # No overlap, skip
             merged.append(interval)
         else:  # Overlap, merge with new
             new = [min(new[0], interval[0]), max(new[1], interval[1])]
     return merged + [new]
  2. Meeting Rooms II (LC 253):
    • Count active intervals using min-heap for end times.

Interview Cheat Sheet:

  • Key Insight: Sorting by start enables one-pass merge.
  • Must-Mention: Time ( O(n \log n) ) (sorting dominates), space ( O(1) ) auxiliary.
  • Edge Tests: Empty input, single interval, all mergable, disjoint intervals.
  • Trap: Forgetting to sort or missing final interval.