You are given a 0-indexed integer array buses of length n, where buses[i] represents the departure time of the ith bus. You are also given a 0-indexed integer array passengers of length m, where passengers[j] represents the arrival time of the jth passenger. All bus departure times are unique. All passenger arrival times are unique.
You are given an integer capacity, which represents the maximum number of passengers that can get on each bus.
When a passenger arrives, they will wait in line for the next available bus. You can get on a bus that departs at x minutes if you arrive at y minutes where y <= x, and the bus is not full. Passengers with the earliest arrival times get on the bus first.
More formally when a bus arrives, either:
capacity or fewer passengers are waiting for a bus, they will all get on the bus, orcapacity passengers with the earliest arrival times will get on the bus.Return the latest time you may arrive at the bus station to catch a bus. You cannot arrive at the same time as another passenger.
Note: The arrays buses and passengers are not necessarily sorted.
Example 1:
Input: buses = [10,20], passengers = [2,17,18,19], capacity = 2 Output: 16 Explanation: Suppose you arrive at time 16. At time 10, the first bus departs with the 0th passenger. At time 20, the second bus departs with you and the 1st passenger. Note that you may not arrive at the same time as another passenger, which is why you must arrive before the 1st passenger to catch the bus.
Example 2:
Input: buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2 Output: 20 Explanation: Suppose you arrive at time 20. At time 10, the first bus departs with the 3rd passenger. At time 20, the second bus departs with the 5th and 1st passengers. At time 30, the third bus departs with the 0th passenger and you. Notice if you had arrived any later, then the 6th passenger would have taken your seat on the third bus.
Constraints:
n == buses.lengthm == passengers.length1 <= n, m, capacity <= 1052 <= buses[i], passengers[i] <= 109buses is unique.passengers is unique.To solve this problem, we employ a two-pointer technique after sorting both the buses and passengers arrays. The bus with the latest departure time will determine your latest possible arrival time.
Throughout, we'll track which passengers can board each bus until no more passengers can fit or there are no waiting passengers. Eventually, check when you can arrive just before the last passenger eligible for the last bus.
Sort the buses and passengers. For each bus, assign passengers whose arrival is before or equal to the departure, counting how many board. Adjust the potential arrival time backward until a free slot is found.
Java
JavaScript
Time Complexity: O((n + m) log(n + m)) due to sorting.
Space Complexity: O(1) for in-place operations.
This method determines the latest optimal time to arrive by initially supposing you arrive at the bus's latest possible time, backtracking from there while enforcing the unique arrival constraint. By leveraging binary search over the passenger list, we assure minimal comparison operations.
Here, binary search is used to minimize list traversal and repetitive checks while iterating for each passenger on a given bus. With optimal sorting, this method converges on the last plausible time you can catch the bus without syncing with another passenger.
C++
Time Complexity: O((n + m) log(n + m))
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Sorted Two-Pointer Approach | Time Complexity: O((n + m) log(n + m)) due to sorting. |
| Greedy Backtrack Approach with Binary Search | Time Complexity: O((n + m) log(n + m)) |
How to EASILY solve LeetCode problems • NeetCode • 427,726 views views
Watch 9 more video solutions →Practice The Latest Time to Catch a Bus with our built-in code editor and test cases.
Practice on FleetCode