#2332

The Latest Time to Catch a Bus

expert · 1180 · lc medium +32 · verified · 30% accepted · 530 likes · top 7%

Description

You are given a 0-indexed integer array buses where buses[i] is the departure time of bus i, a 0-indexed integer array passengers where passengers[j] is the arrival time of passenger j, and an integer capacity (maximum passengers per bus). All departure and arrival times are distinct.

Passengers queue for the next bus and board in order of earliest arrival. A bus takes up to capacity passengers.

Return the latest arrival time that still allows you to board a bus. You may not arrive at the exact same time as another passenger.

Note: 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.

Code

1

2

3

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int: