56. Merge Intervals

At a Glance

• Topic: greedy
• Pattern: Merge Intervals (sort by start, linear merge)
• Difficulty: Medium
• Companies: Google, Facebook, Microsoft, Amazon, Bloomberg
• Frequency: Very High
• LeetCode: 56

Problem (one-liner)

Given a list of closed intervals [start, end], merge all overlapping / touching intervals and return the non-overlapping cover. Input: intervals. Output: merged list (any order is often accepted, but sorted by start is standard).

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• “Merge overlapping intervals”
• Sort by start then sweep extending current merged segment while next.start <= currentEnd
• Touching intervals [a,b] and [b,c] typically merge

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Compare all pairs — O(n²).
• Sort + sweep — O(n log n) time / O(n) output space. <- pick this in interview.

Optimal Solution

Go

package main

import "sort"

func merge(intervals [][]int) [][]int {
	if len(intervals) == 0 {
		return intervals
	}
	sort.Slice(intervals, func(left int, right int) bool {
		return intervals[left][0] < intervals[right][0]
	})
	merged := [][]int{intervals[0]}
	for index := 1; index < len(intervals); index++ {
		lastIndex := len(merged) - 1
		currentStart := intervals[index][0]
		currentEnd := intervals[index][1]
		if currentStart <= merged[lastIndex][1] {
			if currentEnd > merged[lastIndex][1] {
				merged[lastIndex][1] = currentEnd
			}
		} else {
			merged = append(merged, []int{currentStart, currentEnd})
		}
	}
	return merged
}

JavaScript

function merge(intervals) {
	if (intervals.length === 0) return intervals;
	const sorted = [...intervals].sort((left, right) => left[0] - right[0]);
	const merged = [sorted[0]];
	for (let index = 1; index < sorted.length; index++) {
		const lastIndex = merged.length - 1;
		const [currentStart, currentEnd] = sorted[index];
		if (currentStart <= merged[lastIndex][1]) {
			merged[lastIndex][1] = Math.max(merged[lastIndex][1], currentEnd);
		} else {
			merged.push([currentStart, currentEnd]);
		}
	}
	return merged;
}

Walkthrough

intervals = [[1,3],[2,6],[8,10],[15,18]]

Sorted already. Merge [1,3] with [2,6] → [1,6]. Append [8,10], [15,18].

Invariant: after processing sorted prefix, merged covers exactly that prefix’s union with minimal disjoint intervals.

Edge Cases

• Single interval
• Fully nested intervals
• Point intervals

Pitfalls

• Forgetting sort first
• Mutating shared interval slices during iteration if reused elsewhere

Similar Problems

• 435. Non-overlapping Intervals — minimize removals (different objective).
• 057. Insert Interval — merge after single insertion.

Variants

• Return merged length sum — derive from merged list.

Mind-Map Tags

#merge-intervals #sort #sweep-line #medium