Next Available Slot
MediumIntervals
Problem
A conveyor has a list of time slots, slot i being [start, end] with start ≤ end. All start times are distinct.
For each slot i, find the slot j with the smallest start that is at least end_i: the first slot you could move on to after slot i finishes. j may equal i when the slot has zero length. Return an array with the index j for each slot, or -1 when no such slot exists.
Example 1
- Input:
- slots = [[3, 4], [2, 3], [1, 2]]
- Output:
- [-1, 0, 1]
After [2, 3] ends at 3, the slot starting at 3 (index 0) is next. After [1, 2], the slot starting at 2 (index 1). Nothing starts at 4 or later.
Example 2
- Input:
- slots = [[1, 4], [2, 3], [3, 4]]
- Output:
- [-1, 2, -1]
Constraints
- 1 ≤ slots.length ≤ 2·10^4
- -10^6 ≤ start ≤ end ≤ 10^6
- All start values are distinct.
Hint
Show the first hint
For each slot you need a 'smallest value ≥ x' lookup over the start times. Which structure answers that fast?
Walkthrough
How to approach it
01Clarify before coding
- Can j equal i? Yes, when start_i = end_i.
- Are starts unique? Yes, so the answer index is unique.
- Must the output follow the input order? Yes, one answer per original slot.
02Brute force
For every slot, scan all slots and keep the one with the smallest start ≥ end_i.
Cost: O(n²) time: 4·10^8 comparisons for n = 2·10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.