2332. The Latest Time to Catch a Bus
Problem Description
You are at a bus station with a schedule of bus departures and passenger arrivals. Each bus has a specific departure time and can carry a maximum number of passengers, known as the capacity. Passengers arrive at various times and will wait for the next available bus they can board. The goal is to find the latest possible time you can arrive at the station to catch a bus without arriving at the same time as another passenger.
Intuition
The idea is first to sort both the buses
and passengers
arrays since we need to process them in ascending order. The essence of the algorithm is to simulate the boarding process for each bus by letting the earliest arriving passengers board first until the bus reaches capacity or there are no more passengers for that bus.
For each bus, we iterate over the sorted passenger list. We keep track of the count of passengers (c
) that have boarded the bus by decrementing the capacity each time we find an eligible passenger. If a bus becomes full, we keep track of the last passenger who boarded (just before the capacity was reached). If a bus isn't full, it implies that even if you arrive at the time the bus departs, you could still board (assuming no other passenger arrives at exactly that time).
After processing all buses, if the last bus is not full, we can simply return its departure time as the latest time you can arrive. If the last bus is full, we need to find a time just before the last passenger boarded the last bus where there's no other passenger arriving. We do this by decrementing the arrive time of the last boarded passenger until we find a time point where no passenger has arrived.
This effectively gives us the latest time slot where you can arrive and not coincide with any other passenger, ensuring you can board the last bus.
Learn more about Two Pointers, Binary Search and Sorting patterns.
Solution Approach
The solution implements a straightforward approach using sorting and iteration, which can be broken down into the following steps:
-
Sorting: Both
buses
andpassengers
arrays are sorted in increasing order to simplify the simulation of the boarding process. This is done using Python's built-in.sort()
method on the arrays. -
Iterating over buses: We iterate through each bus's departure time in the
buses
array keeping track of a counterc
representing the current carrying capacity of the bus. We also maintain an indexj
to iterate through thepassengers
array. -
Boarding passengers: While the bus has capacity (
c
) and there are waiting passengers (j < len(passengers)
) who arrived on or before the bus's departure time (passengers[j] <= t
), we decrementc
and incrementj
. This simulates passengers boarding the bus. -
Finding the last passenger's arrival time: If the final bus is at full capacity after simulating the boarding process, the variable
ans
is set to the arrival time of the last passenger who boarded. Otherwise,ans
is set to the departure time of the last bus. -
Finding the latest arrival time: We then decrement
ans
until we find a time that does not coincide with any passenger's arrival time. We do this by iterating backwards through the sortedpassengers
array with the indexj
. Whileans
is equal topassengers[j]
, meaning a passenger is already at the station at that time, we decrementans
andj
. -
Result: The
ans
variable, after this loop, will hold the latest time at which you can arrive without coinciding with any passenger and still be able to catch the last bus.
The overall algorithm runs in O(n log n) due to the sorting of buses
and passengers
, followed by a single pass through each, which is O(n).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a specific example to illustrate the solution approach:
Suppose we have 3 buses with departure times buses = [3, 9, 15]
and each bus has a capacity of 2 passengers. Passengers arrive at times passengers = [2, 5, 7, 8]
.
Following the solution approach:
Step 1: Sorting
- Sort
buses
andpassengers
:buses = [3, 9, 15]
(already sorted)passengers = [2, 5, 7, 8]
(already sorted)
Step 2: Iterating over buses
- Start with the first bus at time
3
. Setc
which represents the bus capacity to2
.
Step 3: Boarding passengers
-
First bus (time
3
):passengers[0]
is2
, which is before bus departure. So, one passenger boards.c
becomes1
. -
There are no more passengers that arrived before or at time
3
, so the first bus leaves with one seat empty. -
Second bus (time
9
): Resetc
to2
. -
passengers[1]
is5
andpassengers[2]
is7
. Both passengers board since they arrived before bus departure time.c
becomes0
. -
Last bus (time
15
): Resetc
to2
. -
passengers[3]
is8
. This passenger boards.c
becomes1
.
Step 4: Finding the last passenger's arrival time
- The final bus is not full; it has one remaining capacity. So,
ans
initially is the departure time of the last bus;ans = 15
.
Step 5: Finding the latest arrival time
- Since the last bus is not at full capacity, we do not need to adjust
ans
. You can arrive exactly at time15
and still board.
Step 6: Result
- The latest time you can arrive at the bus station without coinciding with another passenger and being able to catch a bus is
ans = 15
.
In this example, no adjustments were needed in Step 5 because the last bus was not fully boarded. If the final bus had been at full capacity, we would decrement ans
and compare it against the sorted list of passengers
to ensure that there's no conflict before confirming the final ans
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def latest_time_catch_the_bus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
5 # Sort the buses and passengers in ascending order to process them in sequence
6 buses.sort()
7 passengers.sort()
8
9 passenger_index = 0 # index of the current passenger in the sorted list
10 # Iterate through buses to see how many passengers each can pick up
11 for bus_arrival_time in buses:
12 current_capacity = capacity # Track the current bus's remaining capacity
13 # Board passengers until the bus is full or no more passengers for the bus
14 while current_capacity > 0 and passenger_index < len(passengers) and passengers[passenger_index] <= bus_arrival_time:
15 # Load a passenger and decrease the available capacity
16 current_capacity -= 1
17 passenger_index += 1
18
19 # Adjust the index back to the last boarded passenger
20 passenger_index -= 1
21
22 # Latest possible time to catch the bus is either bus's last arrival time
23 # or just a minute before the last passenger boarded if the bus is full
24 latest_time = buses[-1] if current_capacity > 0 else passengers[passenger_index]
25
26 # If the bus is full, find the latest time by subtracting from the last boarded passenger's time,
27 # making sure there's no passenger at that time already
28 while passenger_index >= 0 and passengers[passenger_index] == latest_time:
29 latest_time -= 1
30 passenger_index -= 1
31
32 # Return the latest time a passenger can catch the bus
33 return latest_time
34
1class Solution {
2
3 // Method to find the latest time you can catch the bus without modifying method names as per guidelines.
4 public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
5 // Sort the buses and passengers to process them in order.
6 Arrays.sort(buses);
7 Arrays.sort(passengers);
8
9 // Passenger index and current capacity initialization
10 int passengerIndex = 0, currentCapacity = 0;
11
12 // Iterate through each bus
13 for (int busTime : buses) {
14 // Reset capacity for the new bus
15 currentCapacity = capacity;
16
17 // Load passengers until the bus is either full or all waiting passengers have boarded.
18 while (currentCapacity > 0 && passengerIndex < passengers.length && passengers[passengerIndex] <= busTime) {
19 currentCapacity--;
20 passengerIndex++;
21 }
22 }
23
24 // Decrement to get the last passenger's time or the bus's latest time if it's not full
25 passengerIndex--;
26
27 // Determine the latest time that you can catch the bus
28 int latestTime;
29
30 // If there is capacity left in the last bus, the latest time is the last bus's departure time.
31 // Otherwise, it's the time just before the last passenger boarded.
32 if (currentCapacity > 0) {
33 latestTime = buses[buses.length - 1];
34 } else {
35 latestTime = passengers[passengerIndex];
36 }
37
38 // Ensure that the latest time is not the same as any passenger's arrival time.
39 while (passengerIndex >= 0 && latestTime == passengers[passengerIndex]) {
40 latestTime--;
41 passengerIndex--;
42 }
43
44 // Return the latest time you can catch the bus
45 return latestTime;
46 }
47}
48
1class Solution {
2public:
3 int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
4 // Sort the times when buses arrive
5 sort(buses.begin(), buses.end());
6 // Sort the times when passengers arrive
7 sort(passengers.begin(), passengers.end());
8
9 // Use two pointers for the passenger and bus times
10 int passengerIndex = 0;
11 int currentCapacity = 0;
12
13 // Loop through each bus
14 for (int busTime : buses) {
15 // Reset the capacity for each bus
16 currentCapacity = capacity;
17 // Fill the bus until capacity is reached or no passengers are left to board before the bus time
18 while (currentCapacity && passengerIndex < passengers.size() && passengers[passengerIndex] <= busTime) {
19 --currentCapacity;
20 ++passengerIndex;
21 }
22 }
23
24 // Move back one passenger to see the last passenger who boarded or the bus's last available time
25 --passengerIndex;
26 int latestTime = currentCapacity ? buses.back() : passengers[passengerIndex];
27
28 // Find the latest time you could arrive without coinciding with a passenger time
29 while (passengerIndex >= 0 && latestTime == passengers[passengerIndex]) {
30 --passengerIndex;
31 --latestTime;
32 }
33
34 // Return the latest possible time to catch the bus
35 return latestTime;
36 }
37};
38
1// Sort numeric arrays in ascending order
2function sortNumbers(a: number, b: number): number {
3 return a - b;
4}
5
6// Method to find the latest time to catch the bus
7function latestTimeCatchTheBus(buses: number[], passengers: number[], capacity: number): number {
8 // Sort the bus arrival times
9 buses.sort(sortNumbers);
10 // Sort the passenger arrival times
11 passengers.sort(sortNumbers);
12
13 let passengerIndex: number = 0;
14 let currentCapacity: number = 0;
15
16 // Loop through each bus arrival time
17 for (let busTime of buses) {
18 // Initialize the capacity to the maximum for each bus
19 currentCapacity = capacity;
20
21 // Fill the bus with passengers who arrived before or at the bus time
22 while (currentCapacity > 0 && passengerIndex < passengers.length && passengers[passengerIndex] <= busTime) {
23 --currentCapacity;
24 ++passengerIndex;
25 }
26 }
27
28 // If the last bus has capacity, the latest time is its departure time
29 // Otherwise, start from the last passenger who boarded
30 let latestTime: number = (currentCapacity > 0) ? buses[buses.length - 1] : passengers[passengerIndex - 1];
31
32 // Look for a time just before a passenger arrival time
33 while (passengerIndex > 0 && latestTime === passengers[passengerIndex - 1]) {
34 // Decrement both the passenger index and time to find earlier time slot
35 --passengerIndex;
36 --latestTime;
37 }
38
39 // Return the latest time you could arrive to catch the bus
40 return latestTime;
41}
42
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by the sorting of the buses
and passengers
lists, and the iterations over these lists.
buses.sort()
sorts the list of buses. Sorting a list ofn
elements has a time complexity ofO(n log n)
, wheren
is the number of buses in this context.passengers.sort()
sorts the list of passengers. The sorting has a time complexity ofO(m log m)
, wherem
is the number of passengers.- The for loop iterates over each bus ā this is
O(n)
wheren
is the number of buses. - The nested while loop iterates over the passengers, but it only processes each passenger once in total, not once per bus. Hence, the total number of inner loop iterations is
O(m)
across all iterations of the outer loop, wherem
is the total number of passengers.
Adding these up, we get a time complexity of O(n log n) + O(m log m) + O(n) + O(m)
. Since the O(n log n)
and O(m log m)
terms will be dominant for large n
and m
, we can simplify this to O(n log n + m log m)
.
Space Complexity
The space complexity is determined by the additional memory used by the program.
- The sorting algorithms for both
buses
andpassengers
lists typically have a space complexity ofO(1)
if implemented as an in-place sort such as Timsort (which is the case in Python's sort() function). - The additional variables
c
,j
, andans
use constant space, which adds a space complexity ofO(1)
.
Thus, when not considering the space taken up by the input, the overall space complexity of the code would be O(1)
. However, if considering the space used by the inputs themselves, we must acknowledge that the lists buses
and passengers
use O(n + m)
space.
Therefore, the total space complexity, considering input space, is O(n + m)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!