Intervals & Greedy · 043Medium
Merge Intervals
Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return the non-overlapping intervals covering all the input.
Constraints
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2, 0 <= start <= end <= 10^4
Examples
merge([[1,3],[2,6],[8,10],[15,18]]) -> [[1,6],[8,10],[15,18]] merge([[1,4],[4,5]]) -> [[1,5]] // touching counts as overlapping merge([[1,4],[2,3]]) -> [[1,4]] // fully contained merge([[1,4]]) -> [[1,4]] // single interval, nothing to merge merge([[5,6],[1,2]]) -> [[1,2],[5,6]] // unsorted input, fully disjoint merge([[1,4],[0,4]]) -> [[0,4]] // shared end, later start comes first
Edge cases
- Intervals touching at an endpoint merge.
- One interval fully inside another.
- The input is not sorted.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — repeatedly scan for any overlapping pair until none remain.
- Target
- O(n log n) time — sort by start, then sweep, extending the current interval whenever the next start is <= the current end.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/11-intervals-greedy/043-merge-intervals.js ./practice c 043