The Latest Time to Catch a Bus

The Latest Time to Catch a Bus

What is this problem about?

Imagine you are trying to reach a bus station at the very last possible moment without missing your ride. In "The Latest Time to Catch a Bus," you are given the arrival times of several buses, the arrival times of passengers, and the capacity of each bus. Passengers board the buses in the order they arrive, and each bus has a fixed capacity. You need to find the latest time you could arrive at the station to catch one of the buses, with the additional constraint that you cannot arrive at the same time as any other passenger.

Why is this asked in interviews?

This the Latest Time to Catch a Bus interview question is popular at companies like Microsoft and Amazon because it requires complex simulation and careful handling of boundary conditions. It tests your ability to model a real-world process (queuing and boarding) and then work backward or search for an optimal value within that model. It combines array sorting with a greedy simulation, making it an excellent test of a candidate's overall problem-solving structure.

Algorithmic pattern used

The problem utilizes the Array, Sorting, Two Pointers, Binary Search interview pattern. The first step is to sort both the bus arrival times and the passenger arrival times. Then, you simulate the boarding process greedily: for each bus, fill it with as many passengers as possible who arrived before or at the bus's arrival time, up to its capacity. After the simulation, you look at the last bus and the passengers who boarded it. Your arrival time could either be the bus's arrival time (if the bus isn't full) or right before the last passenger who could have boarded. You then need to decrement your potential arrival time until you find a slot that doesn't conflict with other passengers' arrival times.

Example explanation

Buses arrive at [10, 20], Capacity = 2. Passengers arrive at [2, 17, 18, 19].

1. Bus 1 (at 10): Passenger 2 boards. Bus has 1 spot left, but no more passengers arrived by time 10.
2. Bus 2 (at 20): Passengers 17 and 18 board. The bus is now full. The last passenger to board was at 18. We could try arriving at 17, but someone is already there. We try 16. No one is there. So, the latest time to arrive is 16. If the second bus had arrived at 20 and only passenger 17 boarded, the bus would have an empty slot. We could try arriving at 20. Since no one else is at 20, our result would be 20.

Common mistakes candidates make

A major pitfall in "The Latest Time to Catch a Bus coding problem" is failing to account for the rule that you cannot arrive at the same time as another passenger. Many candidates correctly simulate the bus filling but return a time that is already taken. Another common mistake is not correctly identifying which bus has the "last" available spot—it might not be the very last bus if that bus is completely full of earlier passengers.

Interview preparation tip

Simulation problems require high attention to detail. Practice tracing your logic with small examples and a "pen and paper" approach to ensure your pointers move correctly. Understanding how to use sorting as a preprocessing step to simplify a simulation is a recurring theme in many medium and hard-level interview questions.