Welcome to Subscribe On Youtube
2332. The Latest Time to Catch a Bus
Description
You are given a 0indexed integer array buses
of length n
, where buses[i]
represents the departure time of the i^{th}
bus. You are also given a 0indexed integer array passengers
of length m
, where passengers[j]
represents the arrival time of the j^{th}
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:
 If
capacity
or fewer passengers are waiting for a bus, they will all get on the bus, or  The
capacity
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 0^{th} passenger. At time 20, the second bus departs with you and the 1^{st} passenger. Note that you may not arrive at the same time as another passenger, which is why you must arrive before the 1^{st} 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 3^{rd} passenger. At time 20, the second bus departs with the 5^{th} and 1^{st} passengers. At time 30, the third bus departs with the 0^{th} passenger and you. Notice if you had arrived any later, then the 6^{th} passenger would have taken your seat on the third bus.
Constraints:
n == buses.length
m == passengers.length
1 <= n, m, capacity <= 10^{5}
2 <= buses[i], passengers[i] <= 10^{9}
 Each element in
buses
is unique.  Each element in
passengers
is unique.
Solutions
Solution 1: Simulation
First, we sort, and then use double pointers to simulate the process of passengers getting on the bus: traverse the bus $bus$, passengers follow the principle of “first come, first served”.
After the simulation ends, judge whether the last bus still has seats:

If there are seats, we can arrive at the bus station when the bus departs at $bus[ bus 1]$; if there are people at this time, we can find the time when no one arrives by going forward.  If there are no seats, we can find the last passenger who got on the bus, and find the time when no one arrives by going forward from him.
The time complexity is $O(n \times \log n + m \times \log m)$, and the space complexity is $O(\log n + \log m)$. Where $n$ and $m$ are the numbers of buses and passengers respectively.

class Solution { public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) { Arrays.sort(buses); Arrays.sort(passengers); int j = 0, c = 0; for (int t : buses) { c = capacity; while (c > 0 && j < passengers.length && passengers[j] <= t) { c; ++j; } } j; int ans = c > 0 ? buses[buses.length  1] : passengers[j]; while (j >= 0 && ans == passengers[j]) { ans; j; } return ans; } }

class Solution { public: int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) { sort(buses.begin(), buses.end()); sort(passengers.begin(), passengers.end()); int j = 0, c = 0; for (int t : buses) { c = capacity; while (c && j < passengers.size() && passengers[j] <= t) c, ++j; } j; int ans = c ? buses[buses.size()  1] : passengers[j]; while (~j && ans == passengers[j]) j, ans; return ans; } };

class Solution: def latestTimeCatchTheBus( self, buses: List[int], passengers: List[int], capacity: int ) > int: buses.sort() passengers.sort() j = 0 for t in buses: c = capacity while c and j < len(passengers) and passengers[j] <= t: c, j = c  1, j + 1 j = 1 ans = buses[1] if c else passengers[j] while ~j and passengers[j] == ans: ans, j = ans  1, j  1 return ans

func latestTimeCatchTheBus(buses []int, passengers []int, capacity int) int { sort.Ints(buses) sort.Ints(passengers) j, c := 0, 0 for _, t := range buses { c = capacity for c > 0 && j < len(passengers) && passengers[j] <= t { j++ c } } j ans := buses[len(buses)1] if c == 0 { ans = passengers[j] } for j >= 0 && ans == passengers[j] { ans j } return ans }

function latestTimeCatchTheBus(buses: number[], passengers: number[], capacity: number): number { buses.sort((a, b) => a  b); passengers.sort((a, b) => a  b); let [j, c] = [0, 0]; for (const t of buses) { c = capacity; while (c && j < passengers.length && passengers[j] <= t) { c; ++j; } } j; let ans = c > 0 ? buses.at(1)! : passengers[j]; while (j >= 0 && passengers[j] === ans) { ans; j; } return ans; }

/** * @param {number[]} buses * @param {number[]} passengers * @param {number} capacity * @return {number} */ var latestTimeCatchTheBus = function (buses, passengers, capacity) { buses.sort((a, b) => a  b); passengers.sort((a, b) => a  b); let [j, c] = [0, 0]; for (const t of buses) { c = capacity; while (c && j < passengers.length && passengers[j] <= t) { c; ++j; } } j; let ans = c > 0 ? buses.at(1) : passengers[j]; while (j >= 0 && passengers[j] === ans) { ans; j; } return ans; };