Ferry Longest Wait
Medium · binary search
Passengers turn up at a small ferry pier throughout the day. The list arrivals gives the minute at which each passenger arrives, in non-decreasing order (several passengers can arrive in the same minute).
The ferry company will run at most k sailings today. It picks the departure minute of each sailing. When a sailing departs, it takes every passenger who has arrived by then and has not sailed yet; the boat is big enough for anyone. Everybody must be on some sailing, and nobody can board before they arrive.
A passenger's wait is the departure minute of their sailing minus their arrival minute. The company wants the unluckiest passenger to wait as little as possible.
Return the smallest possible value of the longest wait, in minutes.
Examples
Example 1
Input: arrivals = [1, 2, 3, 10, 11, 12], k = 2
Output: 2
Sail at minute 3 (taking the first three passengers, who wait 2, 1 and 0 minutes) and at minute 12 (the rest wait 2, 1 and 0). With one sailing fewer, someone would wait 11 minutes.
Example 2
Input: arrivals = [4, 4, 4], k = 1
Output: 0
Everyone arrives in minute 4, so one sailing at minute 4 makes nobody wait.
Constraints
- 1 <= len(arrivals) <= 10^5
- 0 <= arrivals[i] <= 10^6
- arrivals[i] <= arrivals[i + 1]
- 1 <= k <= 10^5