Transfer Desk Flight Picks
First index in a sorted array with value at least each query plus an offset
An airport transfer desk has a list of departing flights. The array departures contains their departure times in nondecreasing order. Each flight is identified by its 0-based index in this array, even when several flights depart at the same time.
The array ready contains the time when each passenger reaches the transfer desk. Every passenger needs exactly boarding additional minutes before they can depart. A passenger can take a flight if its departure time is at least their ready time plus boarding.
For each passenger, return the index of the first flight in departures they can take, or -1 if no flight is late enough. Return the results in the same order as ready.
Passengers are handled independently: choosing a flight does not remove it or limit its capacity. Times are integer minutes relative to a shared reference point, so negative times are allowed.
Examples
Example 1
Input: departures = [-10,0,0,15], ready = [-12,-2,0,14], boarding = 2 Output: [0,1,3,-1]
Add the boarding time to each passenger's ready time, then find the first departure that meets that threshold. For the final passenger, every listed flight leaves too early.
Example 2
Input: departures = [5,5,9], ready = [9,5,6], boarding = 0 Output: [2,0,2]
No extra boarding time is required. A flight departing exactly when a passenger is ready is eligible. When eligible flights share a departure time, choose the smaller index.
Example 3
Input: departures = [], ready = [0,10], boarding = 3 Output: [-1,-1]
The departure list is empty, so neither passenger has an eligible flight.
Constraints
- 0 <= departures.length <= 8000
- 0 <= ready.length <= 8000
- departures is sorted in nondecreasing order.
- -10^9 <= departures[i], ready[i] <= 10^9
- 0 <= boarding <= 10^9
- All times and boarding are integers.
The intended complexity is O(n + m log(n + 1)) including input handling, where n is the number of departures and m is the number of passengers. The search work is O(m log(n + 1)), with O(1) auxiliary space excluding the returned list. Do not sort ready, because its order determines the output order.
Hints
Show hint 1Hint 1
For one passenger, departures before their required time are ineligible, and all departures at or after it are eligible.
Show hint 2Hint 2
Binary-search for the first index whose departure is at least ready[i] + boarding. Allow the search to finish just beyond the array.
Follow-up questions
What an interviewer might ask once you have a working solution.
- If ready is also sorted, can you process all passengers with a single forward scan?
- How would you count the eligible flights within a passenger-specific earliest and latest departure window?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem