medium
arrays
sorting
intervals
Given a list of closed intervals [start, end], merge every pair that overlaps or touches and return the disjoint intervals sorted by start value.
Input / output
- Input:
intervals: [integer, integer][] - Output: merged intervals in ascending order
Examples
[[1,3],[2,6],[8,10],[15,18]]returns[[1,6],[8,10],[15,18]].[[1,4],[4,5]]returns[[1,5]]because the endpoints touch.
Constraints
1 <= intervals.length <= 10,000-100,000 <= start <= end <= 100,000- Input intervals may be unsorted and duplicated.
Follow-up If intervals arrived one at a time in sorted order, how would you merge them without storing the entire input?
Examples
Example 1
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Example 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Example 3
Input: intervals = [[1,3],[5,7],[2,4],[6,8]]
Output: [[1,4],[5,8]]
🔒 8 hidden
Running will execute all 11 cases, including 8 hidden ones.