Merge Intervals

Given a list of intervals, merge all overlapping intervals and return the result.

Why this is worth learning

Sorting by start lets a single active interval summarize the union of everything overlapping the current component. Closed intervals that touch at an endpoint merge.

Before coding: one-minute experiment

What does merging [[1,3],[3,5],[8,8]] produce?

Function signature

func MergeIntervals(intervals [][]int) [][]int

Inputs / outputs

• intervals: each element is [start, end] with start <= end.
• Return: merged, non-overlapping intervals sorted by start.

Example

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

Constraints

• 0 <= len(intervals) <= 100_000
• -1_000_000_000 <= start <= end <= 1_000_000_000

Core idea (near-solution)

Sort by start. Then scan and merge into a running interval.

Invariant: the output list is always non-overlapping and sorted.

Algorithm (step-by-step)

1. If the list is empty, return an empty result. Otherwise sort intervals by start (and end as tie-breaker).
2. Initialize current = first interval.
3. For each next interval:
   • If it overlaps (next.start <= current.end), extend current.end.
   • Else, append current and start a new current.
4. Append the final current.

Correctness sketch

After sorting, all completed output intervals lie strictly before the active merged interval, and the active interval is the union of its overlapping component seen so far. If the next start is at most the active end, the intervals overlap or touch; replacing the end by their maximum preserves exactly their union. If the next start exceeds the active end, no later interval can bridge this gap because all later starts are at least as large. The active interval is therefore final and may be emitted. Induction followed by a final flush produces precisely the connected components of the union, in sorted non-overlapping order.

Trace (hand walkthrough)

Example input:
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Walk:
- start [1,3]; merge [2,6] -> [1,6]
- next [8,10] no overlap -> keep
- next [15,18] no overlap -> keep -> [[1,6],[8,10],[15,18]]

Pitfalls to avoid

• Not sorting before merging.
• Using strict < instead of <= for overlap detection.

Debugging lens

Use nested intervals, equal starts, touching endpoints, and an interval entirely containing all others. Update end with max, not by blindly assigning the next end.

Complexity

• Time: O(n log n) due to sorting.
• Extra space: O(n) for the output.

Implementation notes (Go)

• Sort by start ascending.
• Append the last merged interval after the loop.

Contract precision

These are closed intervals: touching endpoints merge. The reference sorts the outer intervals slice in place. The returned merged rows are newly constructed; callers should not assume the original outer order is preserved.

Reconstruction checkpoint

What does merging [[1,3],[3,5],[8,8]] produce?

Return to Intervals · Module quiz