Interval List Intersections
Real-world version: Shared Observation WindowsThe statement here is our own: the same inputs, outputs and technique.
Two telescopes, one under the dome and one out on the ridge, each publish tonight's clear-sky windows as minute marks counted from dusk. dome and ridge hold those windows as [opens, closes] pairs, already ordered by opening mark, and no two windows in the same schedule ever touch: every window closes strictly before the next one in that schedule opens.
A paired reading needs both telescopes clear at once. Report every stretch of time that both schedules cover, again as [opens, closes] pairs ordered by opening mark. A stretch that comes down to a single minute mark, where opens equals closes, still counts as coverage and must be reported.
Either schedule may be empty, though not both. When the two schedules never coincide, return an empty list.
Examples
Example 1
- Input
- dome = [[2, 6], [10, 14]], ridge = [[6, 9], [13, 20]]
- Output
- [[6, 6], [13, 14]]
The first two windows meet only at mark 6, which still counts, and the later pair overlaps from mark 13 until the dome window closes at 14.
Example 2
- Input
- dome = [[2, 20]], ridge = [[3, 5], [8, 9], [12, 25]]
- Output
- [[3, 5], [8, 9], [12, 20]]
One long dome window swallows the first two ridge windows whole and clips the third at mark 20.
Example 3
- Input
- dome = [[1, 2]], ridge = [[3, 4]]
- Output
- []
The dome window has already closed before the ridge window opens, so nothing is covered twice.
Constraints
- 0 <= dome.length, ridge.length <= 1000
- dome.length + ridge.length >= 1
- 0 <= opens < closes <= 10^9 for every window
- Within one schedule the windows are sorted and disjoint: each window's closing mark is strictly less than the next window's opening mark.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def shared_windows(dome: list[list[int]], ridge: list[list[int]]) -> list[list[int]]:public int[][] sharedWindows(int[][] dome, int[][] ridge)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's