Interval problems almost always start with one move: sort by start. Once sorted, an interval can only overlap the one immediately before it in the merged output, so a single pass finishes the job.
Given a list of intervals [start, end] (inclusive), merge all overlapping intervals and return a list of non-overlapping intervals sorted by start. Intervals that merely touch, such as [1, 4] and [4, 5], count as overlapping.
Examples
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Constraints
0 <= len(intervals) <= 10**4start <= endfor every interval; the input is not necessarily sorted.- Aim for O(n log n) time (dominated by the sort).
Goals
- Sort intervals by start so that overlaps are always adjacent
- Compare each interval with the last merged one and either extend it or start a new one
- Handle touching intervals and fully-contained intervals correctly