Merge Intervals
Medium · Intervals · Array · Sorting
Problem
Given a list of intervals [start, end], merge every group that overlaps and return the resulting non-overlapping intervals, sorted by start.
Intervals that merely touch — such as [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, so they become [1,6].
Input: intervals = [[1,4],[4,5]] Output: [[1,5]]
Touching endpoints merge.
Constraints
- 1 <= len(intervals) <= 10^4
- intervals[i] == [start_i, end_i]
- 0 <= start_i <= end_i <= 10^4
Approaches
- Sweep line over endpoints — time O(n log n), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
