Merge Intervals
Medium· Sorting· Sweep
Problem
Given a list of intervals [start, end], merge every group of overlapping intervals and return the resulting non-overlapping intervals. Intervals that merely touch, like [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]]
[1,3] and [2,6] overlap and become [1,6].
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Constraints
- • 1 <= intervals.length <= 10^4
- • 0 <= start <= end <= 10^4
Hints & approach
Hint 1
Overlaps are easy to spot once intervals are in a useful order.
Hint 2
Sort by start; then an interval can only overlap the last merged one.
Approachtry the hints first
Sort intervals by start. Walk through them keeping a result list: if the current interval starts at or before the end of the last merged interval, extend that end to the maximum of both ends; otherwise append the current interval as a new block. Sorting guarantees nothing later can overlap an earlier closed block.
Time O(n log n) · Space O(n)