2332. The Latest Time to Catch a Bus

MediumArrayTwo PointersBinary SearchSorting
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the following shows the order of node visit in a Breadth-first Search?

Solution Approach

The solution implements a straightforward approach using sorting and iteration, which can be broken down into the following steps:

  1. Sorting: Both buses and passengers 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.

  2. Iterating over buses: We iterate through each bus's departure time in the buses array keeping track of a counter c representing the current carrying capacity of the bus. We also maintain an index j to iterate through the passengers array.

  3. 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 decrement c and increment j. This simulates passengers boarding the bus.

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

  5. 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 sorted passengers array with the index j. While ans is equal to passengers[j], meaning a passenger is already at the station at that time, we decrement ans and j.

  6. 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).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example 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 and passengers: 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. Set c which represents the bus capacity to 2.

Step 3: Boarding passengers

  • First bus (time 3): passengers[0] is 2, which is before bus departure. So, one passenger boards. c becomes 1.

  • 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): Reset c to 2.

  • passengers[1] is 5 and passengers[2] is 7. Both passengers board since they arrived before bus departure time. c becomes 0.

  • Last bus (time 15): Reset c to 2.

  • passengers[3] is 8. This passenger boards. c becomes 1.

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 time 15 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following is a good use case for backtracking?

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.

  1. buses.sort() sorts the list of buses. Sorting a list of n elements has a time complexity of O(n log n), where n is the number of buses in this context.
  2. passengers.sort() sorts the list of passengers. The sorting has a time complexity of O(m log m), where m is the number of passengers.
  3. The for loop iterates over each bus โ€“ this is O(n) where n is the number of buses.
  4. 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, where m 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.

  1. The sorting algorithms for both buses and passengers lists typically have a space complexity of O(1) if implemented as an in-place sort such as Timsort (which is the case in Python's sort() function).
  2. The additional variables c, j, and ans use constant space, which adds a space complexity of O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 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 Two pointers is a common interview technique

Binary Search Speedrun

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

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

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ