Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Merge Intervals (LC 56)

Problem Statement

You are given an array of intervals intervals[i] = [start_i, end_i]. Merge all overlapping intervals and return a list of non-overlapping intervals that cover all the input ranges.

Example 1:

Input:  [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap → merge to [1,6].

Example 2:

Input:  [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Touching intervals count as overlapping.

Constraints:

• 1 <= intervals.length <= 10^4
• 0 <= start_i <= end_i <= 10^4

Difficulty: Medium

---

Pattern Recognition

• Input structure: unsorted list of interval pairs.
• What are we producing? a minimal cover of non-overlapping merged intervals.
• Pattern: sort-and-sweep. Once intervals are sorted by start, each new interval either extends the last merged one (overlap) or begins a new merged group.
• Why: after sorting by start, overlap is detectable in O(1) per step because you only need to compare the current interval's start with the last merged interval's end.

---

Approach

Brute Force

Repeatedly scan the list looking for any pair that overlaps, merge them in place, and restart the scan. O(n^2) or worse because you potentially re-scan after every merge.

Optimal — Sort Then Sweep

Key Insight: After sorting by start, two intervals overlap if and only if the current interval's start is less than or equal to the last merged interval's end. You never need to look further back.

Steps:

1. Sort intervals by start ascending.
2. Initialize merged = [intervals[0]].
3. For each subsequent interval [s, e]:
   • If s <= merged[-1].end, overlap — update merged[-1].end = max(merged[-1].end, e).
   • Otherwise, push [s, e] as a new group.
4. Return merged.

Time: O(n log n) for the sort, O(n) for the sweep → O(n log n) total. Space: O(n) for the output (O(log n) or O(n) auxiliary depending on sort implementation).

---

Walkthrough

Input: [[1,3],[2,6],[8,10],[15,18],[4,5]].

Sort by start: [[1,3],[2,6],[4,5],[8,10],[15,18]].

Step	Incoming	Last merged	Action	Merged state
0	[1,3]	—	seed	[[1,3]]
1	[2,6]	[1,3]	2 <= 3, extend end to max(3,6)=6	[[1,6]]
2	[4,5]	[1,6]	4 <= 6, extend end to max(6,5)=6	[[1,6]]
3	[8,10]	[1,6]	8 > 6, new group	[[1,6],[8,10]]
4	[15,18]	[8,10]	15 > 10, new group	[[1,6],[8,10],[15,18]]

Notice step 2: taking max(end, e) instead of just e — crucial for intervals fully contained within the last merged one.

---

Implementation

TypeScript

function merge(intervals: number[][]): number[][] {
    if (intervals.length === 0) return [];
    intervals.sort((a, b) => a[0] - b[0]);

    const merged: number[][] = [intervals[0].slice()];
    for (let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];
        const last = merged[merged.length - 1];
        if (start <= last[1]) {
            last[1] = Math.max(last[1], end); // overlap — extend end
        } else {
            merged.push([start, end]);         // disjoint — new group
        }
    }
    return merged;
}

C++

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });

    vector<vector<int>> merged;
    merged.push_back(intervals[0]);
    for (int i = 1; i < (int)intervals.size(); i++) {
        int start = intervals[i][0], end = intervals[i][1];
        auto& last = merged.back();
        if (start <= last[1]) {
            last[1] = max(last[1], end);
        } else {
            merged.push_back({start, end});
        }
    }
    return merged;
}

Watch out:

1. Using last[1] = end instead of max(last[1], end) silently drops the case where the incoming interval is fully inside the last merged one.
2. The overlap test must be <=, not <, because touching intervals like [1,4] and [4,5] are considered overlapping in this problem.
3. Mutating the first element in-place after merged = [intervals[0]] mutates the input. Clone with slice() / copy if the caller needs the original.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2)	O(n)
Sort + Sweep	O(n log n)	O(n)

Bottleneck: the sort. You cannot avoid it without stronger input guarantees (e.g., values bounded by k lets you bucket-sort in O(n + k)).

---

Edge Cases

1. Empty input — return []. Guard the seed line.
2. Single interval — returned unchanged.
3. All intervals identical — should merge into one. max handles it.
4. Fully contained intervals — [[1,10],[2,3]] must return [[1,10]]. The max(end, e) step protects you.
5. Touching endpoints — [[1,4],[4,5]] → [[1,5]]. Test must be <=.
6. Already sorted / reverse-sorted inputs — sort is stable, no extra logic needed.

---

Related Problems

• LC 57 — Insert Interval — Same sweep with a pre-sorted input and an extra interval to inject. O(n).
• LC 252 / 253 — Meeting Rooms I/II — I: determine if any overlap exists. II: count max concurrent overlaps (heap or sweep line).
• LC 435 — Non-overlapping Intervals — Greedy by end, count removals. Different sort key, same family.
• LC 1288 — Remove Covered Intervals — Sort by start ascending, end descending, sweep tracking the max end.

---

What Is Expected at Each Level

Junior: Recognize that sorting is the unlock, handle touching endpoints, write the core loop. May need a nudge on the contained-interval edge case.

Mid-level: Clean, bug-free code on first pass. Correctly pick <= over <, explain O(n log n), handle containment without prompting.

Senior (L4 target): Anticipate follow-ups — streaming input (heap/TreeMap), parallel merging (map-reduce style), interval trees for frequent insert/query. Discuss sort-stability, in-place vs copy, and the impact of using a sentinel interval. Be ready to pivot to Insert Interval or Meeting Rooms II on the fly.