Medium
Merge Intervals
- Time limit
- 2 s
- Memory limit
- 256 MB
- Estimated
- 20 min
- Scheduling and Intervals
Description
Description
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the merged, non-overlapping intervals.
Two intervals [a, b] and [c, d] overlap if c <= b. Intervals that merely touch (b == c) are considered overlapping and must be merged.
Return the merged intervals sorted by their start value.
Examples
Example 1
- Input:
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] - Output:
[[1, 6], [8, 10], [15, 18]] - Explanation:
[1, 3]and[2, 6]overlap, so they merge into[1, 6].
Example 2
- Input:
intervals = [[1, 4], [4, 5]] - Output:
[[1, 5]] - Explanation: The intervals touch at
4, so they merge.
Example 3
Constraints
0 <= intervals.length <= 10000intervals[i].length == 20 <= start_i <= end_i <= 100000- The input intervals may be given in any order.
- The output must be sorted by start value and contain no overlaps.
Sample cases
3Sample 1
Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Expected output
[[1,6],[8,10],[15,18]]
Sample 2
Input
intervals = [[1,4],[4,5]]
Expected output
[[1,5]]
Skills and languages
Patterns
- Merge Intervals
Languages
- Python 3
Solve this problem
Create a free account to write, run and submit your solution.
- Write Python or Java in the browser, with your draft saved as you type
- Run your code on the examples as often as you like
- Submit to a sandboxed judge and see exactly which case failed
- Ask the AI mentor for a hint without being handed the answer