Lv.2arraysorting
Merge Intervals
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given an array of closed intervals intervals[i] = [start, end], merge all intervals that overlap or touch and return the
result sorted by start. [1, 3] and [3, 5] touch and become [1, 5]; [1, 2] and [3, 4] stay separate.
Examples
| intervals | result |
|---|---|
[[1, 3], [8, 10], [2, 6], [15, 18]] | [[1, 6], [8, 10], [15, 18]] |
[[1, 4], [4, 5]] | [[1, 5]] |
[[5, 7], [1, 2], [3, 4]] | [[1, 2], [3, 4], [5, 7]] |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(intervals: int[][]) → int[][]
Constraints
-
intervals.length - ; the input is unsorted and may repeat intervals.
Expected complexity
- Time
- O(N log N)
- Space
- O(N)
Examples
| intervals | Expected |
|---|---|
[[1,3],[8,10],[2,6],[15,18]] | [[1,6],[8,10],[15,18]] |
[[1,4],[4,5]] | [[1,5]] |
[[5,7],[1,2],[3,4]] | [[1,2],[3,4],[5,7]] |
Hint
Hint
Sort by start; mergeable intervals become adjacent. Sweep while keeping the current [curS, curE] and extend with
curE = max(curE, end) whenever start <= curE. Comparing all pairs is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 298 ms | estimated |
| C++ (GCC, gnu++23) | 298 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 3244 ms | derived |
| Kotlin 2.4 (JVM) | 1596 ms | estimated |
| C# 14 (.NET 10) | 1596 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |