#2332

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

The Latest Time to Catch a Bus

Find the latest time to catch a bus based on departure times, passenger arrivals, and capacity using binary search over valid times.

array two pointers binary search sorting

Problem Statement

You are given two arrays: buses and passengers, where buses[i] represents the departure time of the ith bus, and passengers[j] represents the arrival time of the jth passenger. Each bus can only carry a certain number of passengers, and they board the bus in order of their arrival times. You must determine the latest time you can arrive at a bus stop before the buses depart and still be able to board a bus.

Each bus has a maximum capacity, and passengers will get on the next available bus according to their arrival times. If you arrive at a time that would conflict with another passenger who is getting on, or if the bus is full, you cannot board. The goal is to calculate the latest possible time you can arrive at the bus stop and still be able to catch a bus.

Examples

Example 1

Input: buses = [10,20], passengers = [2,17,18,19], capacity = 2

Output: 16

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

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.length
m == passengers.length
1 <= n, m, capacity <= 105
2 <= buses[i], passengers[i] <= 109
Each element in buses is unique.
Each element in passengers is unique.

Solution Approach

Sort Buses and Passengers

Begin by sorting both the buses and passengers arrays. This is crucial because passengers board the buses in the order of their arrival times, and buses depart in sorted order. Sorting ensures that we can efficiently find the time at which a passenger would board a bus.

Binary Search Over Valid Times

Use binary search over the possible arrival times to find the latest time you can arrive at the bus stop. For each mid point in the binary search, check if you can board a bus. The binary search narrows down the latest possible time by checking whether the current time allows you to board without exceeding the bus's capacity.

Simulate Boarding for Each Time

For each candidate arrival time determined by the binary search, simulate the process of passengers boarding the buses. Ensure that the number of passengers on the bus does not exceed the bus's capacity. This will allow you to verify whether a given time is valid for catching a bus.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n log m), where n is the number of buses and m is the number of passengers. The binary search over possible times takes O(log m), and for each check, we simulate the boarding process which takes O(n). Sorting the buses and passengers takes O(n log n) and O(m log m), respectively, but these are dominated by the binary search and simulation steps.

What Interviewers Usually Probe

Is the candidate able to identify the correct pattern of binary search over valid answer space?
Does the candidate understand the importance of sorting to enable efficient boarding simulation?
Can the candidate simulate the boarding process to ensure the bus is not overfilled while respecting passenger arrival times?

Common Pitfalls or Variants

Common pitfalls

Failing to sort the buses and passengers arrays before attempting to board the buses.
Incorrectly simulating the boarding process and not correctly managing bus capacity.
Misunderstanding the problem's constraints, such as the need for binary search over the valid arrival times.

Follow-up variants

Consider a variant where buses may have different capacities.
Handle the case where multiple passengers arrive exactly at the same time.
Modify the problem so that you can board any bus without following the earliest arrival rule.

FAQ

What is the primary pattern to solve The Latest Time to Catch a Bus?

The primary pattern is binary search over the valid answer space, focusing on the latest time you can arrive at the bus stop without exceeding bus capacity.

How does sorting affect the solution to this problem?

Sorting the buses and passengers arrays allows you to efficiently simulate the boarding process and check for available seats in a time-efficient manner.

What is the time complexity of the optimal solution?

The time complexity is O(n log m), where n is the number of buses and m is the number of passengers.

Can binary search really help solve this problem?

Yes, binary search is used over the possible arrival times, narrowing down the latest time you can catch a bus while ensuring the buses are not overfilled.

What common mistakes should I avoid in this problem?

Avoid failing to sort the buses and passengers arrays, mismanaging the bus capacity during simulation, and not implementing binary search over the valid answer space.

terminal

Solution

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".

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

Continue Practicing

#2300 successful pairs of spells and potions #2234 maximum total beauty of the gardens #2563 count the number of fair pairs