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.
Worked 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]]
Hints
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.
Solution approach
- 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.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n log n) time; O(n) auxiliary space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗