Merge Intervals
Module 14 · Sorting
Problem
Given a collection of intervals [start, end], merge all overlapping
intervals and return the resulting non-overlapping set.
Examples
Example 1
Input
[[1,3],[2,6],[8,10],[15,18]]Output[[1,6],[8,10],[15,18]]Example 2
Input
[[1,4],[4,5]]Output[[1,5]]Explanation. touching counts as overlapping
Constraints
1 ≤ n ≤ 10⁴ · intervals given in arbitrary order.
Attempt it first
The whole problem is exactly one insight away: overlapping intervals are hard to detect in arbitrary order, but trivial once sorted by start time — overlaps can then only happen between neighbors. Find the one-line reduction before opening the hint.