Nearest Following Slot

Medium

A meeting room schedule lists slots slots[i] = [start, end]. No two slots share a start. For each slot i, find the slot j that starts no earlier than slot i ends (start_j ≥ end_i) and, among all such slots, starts the earliest. A slot may turn out to be its own match (j = i). Return a list whose i-th entry is the index of that slot j, or -1 if there is no such slot.

Example 1

slots=[[9, 11], [1, 4], [5, 9], [4, 6]] → [-1, 3, 0, 0]

After [1, 4], the earliest start is [4, 6] (index 3); after [5, 9] it is [9, 11] (index 0); after [4, 6] also [9, 11]; nothing starts after [9, 11].

Example 2

slots=[[3, 3], [0, 8]] → [0, -1]

The slot [3, 3] ends where it starts, so it qualifies as its own follower. Nothing starts after [0, 8].

Example 3

slots=[[-2, 5]] → [-1]

Constraints

1 ≤ len(slots) ≤ 2·10⁴
len(slots[i]) == 2
-10⁶ ≤ start ≤ end ≤ 10⁶
All slot starts are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Sorting

Similar problems

Triples Under a Limit Medium K-th Smallest in a Sorted Grid Medium Warm Every Cabin Medium Pairs With a Fixed Gap Medium Stick Triples That Form a Triangle Medium

Input

slots=[[9, 11], [1, 4], [5, 9], [4, 6]]

Expected

[-1, 3, 0, 0]

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