Merge Intervals
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
