Funcia
Lv.2arrayintervalstwo-pointers

Interval List Intersections

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

first and second are lists of closed intervals [start, end]. Within each list the intervals are sorted by start and pairwise disjoint and non-touching (each end < the next start). Return the intersection of the two lists — every maximal interval covered by both — sorted by start. A single shared point t is reported as [t, t]. Return an empty array if there is no overlap.

Examples

firstsecondresult
[[0, 2], [5, 10], [13, 23], [24, 25]][[1, 5], [8, 12], [15, 24], [25, 26]][[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]
[[1, 3], [5, 9]][[10, 12]][]
[[1, 7]][[3, 10]][[3, 7]]

Example 1 — [5, 10] and [1, 5] meet only at 5, giving [5, 5].

Example 2 — The only interval of second comes after everything in first.

Example 3 — The overlap is [3, 7].

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(first: int[][], second: int[][]) → int[][]

Constraints

  • 1≤1 \le first.length, second.length ≤100,000\le 100{,}000
  • Each element is [start, end] with 0≤0 \le start ≤\le end ≤109\le 10^9
  • Within each list, the end of interval i < the start of interval i+1

Expected complexity

Time
O(N + M)
Space
O(N + M)

Examples

firstsecondExpected
[[0,2],[5,10],[13,23],[24,25]][[1,5],[8,12],[15,24],[25,26]][[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
[[1,3],[5,9]][[10,12]][]
[[1,7]][[3,10]][[3,7]]

Hint

Hint

The intersection of [a, b] and [c, d] is [max(a, c), min(b, d)] when that is non-empty. Walk both sorted lists with two pointers like a merge: record the overlap of the current pair, then advance whichever interval ends first — it cannot meet anything later in the other list. That is O(N+M)O(N + M); comparing all pairs is O(NM)O(NM) and times out.

Time limits per language

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

Test groups

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

No result yet. Run or submit your code.