Interval List Intersections
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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
| first | second | result |
|---|---|---|
[[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
-
first.length,second.length - Each element is
[start, end]withstartend - Within each list, the
endof intervali< thestartof intervali+1
Expected complexity
- Time
- O(N + M)
- Space
- O(N + M)
Examples
| first | second | Expected |
|---|---|---|
[[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 ; comparing all pairs is and times out.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 240 ms | estimated |
| C++ (GCC, gnu++23) | 240 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 2686 ms | derived |
| Kotlin 2.4 (JVM) | 1480 ms | estimated |
| C# 14 (.NET 10) | 1480 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |