Funcia
Lv.2arraysorting

Merge Intervals

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

intervalsresult
[[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

  • 1≤1 \le intervals.length ≤200,000\le 200{,}000
  • 0≤start≤end≤1090 \le start \le end \le 10^9; the input is unsorted and may repeat intervals.

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

intervalsExpected
[[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 O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)298 msestimated
C++ (GCC, gnu++23)298 msderived
Python 3.131000 msderived
Java 253244 msderived
Kotlin 2.4 (JVM)1596 msestimated
C# 14 (.NET 10)1596 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.