Earliest Common Free Window

Medium

Two colleagues want to set up a call. Each has a list of free intervals, free_a and free_b, where [start, end] means "free from time start until time end". One person's intervals never overlap or touch each other, but they may come in any order. The call must last exactly length: a stretch [s, s + length] that lies entirely inside a free interval of each person. Return the earliest such stretch as [s, s + length], or an empty list if there is no suitable time.

Example 1

free_a=[[30, 45], [90, 150]], free_b=[[0, 40], [100, 120]], length=10 → [30, 40]

Both are free from 30 to 40, exactly 10 minutes, so [30, 40] works and nothing earlier does.

Example 2

free_a=[[30, 45], [90, 150]], free_b=[[0, 40], [100, 120]], length=15 → [100, 115]

The shared window [30, 40] is now too short; the next one is [100, 120], giving [100, 115].

Example 3

free_a=[[5, 8]], free_b=[[8, 20]], length=1 → []

The windows touch only at time 8, so there is no shared stretch of length 1.

Constraints

1 ≤ len(free_a), len(free_b) ≤ 10⁴
0 ≤ start < end ≤ 10⁹
1 ≤ length ≤ 10⁶
one person's intervals neither overlap nor touch

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Sorting

Similar problems

Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Flags in Three Colors Medium Studios for Recording Sessions Medium

Input

free_a=[[30, 45], [90, 150]], free_b=[[0, 40], [100, 120]], length=10

Expected

[30, 40]

Run checks the first 3 tests in your browser. Submit checks all 106 tests on the server, hidden ones included.