Next Ferry Out
Easy · binary search
A harbour keeps a timetable of ferry departures. departures lists the departure times in minutes after midnight, from earliest to latest. Several ferries can leave at the same minute, so a time may appear more than once.
Passengers reach the quay at the times in arrivals. Each passenger boards the earliest ferry that leaves at their arrival time or later.
Return a list with one number per passenger, in the same order as arrivals: the departure time of the ferry they board, or -1 if every ferry has already left. Passengers do not affect each other, so a ferry never fills up.
Examples
Example 1
Input: departures = [10, 25, 25, 40], arrivals = [5, 25, 26, 41]
Output: [10, 25, 40, -1]
Arriving at minute 5 you board the 10 ferry. At minute 25 a ferry is just leaving, so you catch it. At minute 26 the next one is at 40. At minute 41 nothing is left.
Example 2
Input: departures = [100], arrivals = [100, 101]
Output: [100, -1]
Constraints
- 1 <= len(departures) <= 10^4
- 1 <= len(arrivals) <= 10^4
- 0 <= departures[i], arrivals[j] <= 10^9
- departures is sorted in ascending order (equal values allowed).