Merge Intervals
Part of Practice: Insert & Merge
You are given a list of intervals, each a pair [start, end], in no particular order and possibly overlapping. Merge every group of overlapping intervals into a single interval that covers them, and return the resulting list of non-overlapping intervals.
Constraints that matter: up to 10,000 intervals, and intervals that merely touch (like [1, 4] and [4, 5]) count as overlapping and must merge. Comparing every pair of intervals is O(n²); sorting first turns the problem into a single sweep.
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 merge into [1,6]. The other two touch nothing.
- Input:
- intervals = [[1,4],[4,5]]
- Output:
- [[1,5]]
Sharing the single point 4 counts as overlapping.
- Input:
- intervals = [[4,7],[1,4]]
- Output:
- [[1,7]]
After sorting by start the intervals are [1,4], [4,7], which touch and merge.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.