The Latest Time to Catch a Bus

Medium

Asked by:

25 views

Topics:

ArraysBinary SearchGreedy Algorithms

You are given a 0-indexed integer array buses of length n, where buses[i] represents the departure time of the i^th bus. You are also given a 0-indexed integer array passengers of length m, where passengers[j] represents the arrival time of the j^th passenger. All bus departure times are unique. All passenger arrival times are unique.

You are given an integer capacity, which represents the maximum number of passengers that can get on each bus.

When a passenger arrives, they will wait in line for the next available bus. You can get on a bus that departs at x minutes if you arrive at y minutes where y <= x, and the bus is not full. Passengers with the earliest arrival times get on the bus first.

More formally when a bus arrives, either:

If capacity or fewer passengers are waiting for a bus, they will all get on the bus, or
The capacity passengers with the earliest arrival times will get on the bus.

Return the latest time you may arrive at the bus station to catch a bus. You cannot arrive at the same time as another passenger.

Note: The arrays 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 0^th passenger. 
At time 20, the second bus departs with you and the 1^st passenger.
Note that you may not arrive at the same time as another passenger, which is why you must arrive before the 1^st 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 3^rd passenger. 
At time 20, the second bus departs with the 5^th and 1^st passengers.
At time 30, the third bus departs with the 0^th passenger and you.
Notice if you had arrived any later, then the 6^th passenger would have taken your seat on the third bus.

Constraints:

n == buses.length
m == passengers.length
1 <= n, m, capacity <= 10⁵
2 <= buses[i], passengers[i] <= 10⁹
Each element in buses is unique.
Each element in passengers is unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of `buses` and `passengers` arrays? Can they be negative, zero, or very large?
Are the `buses` and `passengers` arrays guaranteed to be sorted? If not, do I need to sort them?
If a passenger can arrive at the exact same time as a bus departs, are they allowed to board the bus or must they arrive strictly before the departure time?
If there are multiple possible latest arrival times for a passenger to catch a bus, should I return the earliest or latest of those times?
If a passenger cannot catch any bus, what value should I return? Is there a specific value indicating no possible solution?

Brute Force Solution

Approach

We need to figure out the very last moment someone can arrive at a bus stop and still catch a bus. The brute force way is like trying every possible arrival time, one by one, to see if it works. We check each time to ensure the person can catch a bus without delaying anyone else.

Here's how the algorithm would work step-by-step:

Start with the latest possible time a person could arrive.
Check if a person arriving at that time can catch a bus without making the bus late or bumping someone else.
If they can, then this is a possible answer.
If they cannot, try the next earliest time.
Keep going, checking each earlier time, until you find a time that works.
The first time you find that works is the latest possible time.

Code Implementation

def the_latest_time_to_catch_the_bus(buses, passengers, bus_capacity):
    buses.sort()
    passengers.sort()

    latest_possible_time = buses[-1]

    for arrival_time in range(latest_possible_time, 0, -1):
        temp_passengers = passengers[:] 
        bus_index = 0
        passenger_index = 0
        passengers_on_bus = 0

        # Simulate the bus arrival and passenger boarding process
        while bus_index < len(buses) and passenger_index < len(temp_passengers):
            if temp_passengers[passenger_index] <= buses[bus_index]:
                passengers_on_bus += 1
                passenger_index += 1
            else:
                bus_index += 1
                passengers_on_bus = 0

            if passengers_on_bus == bus_capacity:
                bus_index += 1
                passengers_on_bus = 0

        # Check if the new arrival can board a bus
        bus_index = 0
        passenger_index = 0
        passengers_on_bus = 0

        while bus_index < len(buses) and passenger_index < len(temp_passengers):
            if temp_passengers[passenger_index] <= buses[bus_index]:
                if temp_passengers[passenger_index] < arrival_time:
                    passengers_on_bus += 1
                else:
                    break
                passenger_index += 1
            else:
                bus_index += 1
                passengers_on_bus = 0

            if passengers_on_bus == bus_capacity:
                bus_index += 1
                passengers_on_bus = 0

        # Check if the arrival time is valid.
        can_board = True

        bus_index = 0
        passenger_index = 0
        passengers_on_bus = 0

        while bus_index < len(buses) and passenger_index < len(temp_passengers):
            if temp_passengers[passenger_index] <= buses[bus_index]:
                passengers_on_bus += 1
                if temp_passengers[passenger_index] == arrival_time:
                    can_board = False
                    break
                passenger_index += 1
            else:
                bus_index += 1
                passengers_on_bus = 0

            if passengers_on_bus == bus_capacity:
                bus_index += 1
                passengers_on_bus = 0
        
        if not can_board:
            continue

        bus_index = 0
        passenger_index = 0
        passengers_on_bus = 0

        while bus_index < len(buses) and passenger_index < len(temp_passengers):
            if temp_passengers[passenger_index] <= buses[bus_index]:
                passengers_on_bus += 1
                passenger_index += 1
            else:
                bus_index += 1
                passengers_on_bus = 0

            if passengers_on_bus == bus_capacity:
                bus_index += 1
                passengers_on_bus = 0

        # Check if someone is already arriving at that time.
        if arrival_time not in passengers:

            # Ensures we don't return duplicates, since we decrement the arrival time
            return arrival_time

        # Try one second earlier to avoid collision with existing passengers
        arrival_time -= 1

        # Check if an earlier time is still valid
        temp_passengers = passengers[:]
        bus_index = 0
        passenger_index = 0
        passengers_on_bus = 0
        while bus_index < len(buses) and passenger_index < len(temp_passengers):
            if temp_passengers[passenger_index] <= buses[bus_index]:
                passengers_on_bus += 1
                passenger_index += 1
            else:
                bus_index += 1
                passengers_on_bus = 0

            if passengers_on_bus == bus_capacity:
                bus_index += 1
                passengers_on_bus = 0

        # Check again if the arrival time is valid.
        can_board = True
        bus_index = 0
        passenger_index = 0
        passengers_on_bus = 0

        while bus_index < len(buses) and passenger_index < len(temp_passengers):
            if temp_passengers[passenger_index] <= buses[bus_index]:
                passengers_on_bus += 1
                if temp_passengers[passenger_index] == arrival_time:
                    can_board = False
                    break
                passenger_index += 1
            else:
                bus_index += 1
                passengers_on_bus = 0

            if passengers_on_bus == bus_capacity:
                bus_index += 1
                passengers_on_bus = 0

        if not can_board:
            continue

        bus_index = 0
        passenger_index = 0
        passengers_on_bus = 0

        while bus_index < len(buses) and passenger_index < len(temp_passengers):
            if temp_passengers[passenger_index] <= buses[bus_index]:
                passengers_on_bus += 1
                passenger_index += 1
            else:
                bus_index += 1
                passengers_on_bus = 0

            if passengers_on_bus == bus_capacity:
                bus_index += 1
                passengers_on_bus = 0

        # Try one second earlier to avoid collision with existing passengers
        return arrival_time

    return 0

Big(O) Analysis

Time Complexity

O(n*m) – We iterate downwards from the maximum possible arrival time, potentially checking up to m times where m is the maximum possible arrival time. For each potential arrival time, we iterate through all the bus arrival times to see if the passenger can catch any bus and all the passenger arrival times to see if they are bumped from boarding a bus. Thus we are iterating a total of n times with n being the total number of elements in the bus array added to the passengers array. In total the runtime of the algorithm is O(n*m). However, m can be considered in the scale of input n.

Space Complexity

O(1) – The brute force approach described involves iteratively checking each arrival time. No additional data structures like lists or hash maps are created to store intermediate results or visited times. Only a few variables are needed to track the current arrival time being checked and possibly a boolean flag to indicate if a suitable arrival time has been found. Therefore, the auxiliary space used remains constant irrespective of the input size, making the space complexity O(1).

Optimal Solution

Approach

The key is to first ensure everything is in order, making it easier to find the best possible time. Then, work backward from the latest bus, trying to board passengers at the latest possible moment without conflict.

Here's how the algorithm would work step-by-step:

First, organize the bus arrival times and passenger arrival times in ascending order.
Begin with the last bus and work backwards towards the earlier buses.
For each bus, attempt to fill it with passengers arriving at the latest possible times.
When a passenger can board the bus, mark the time as occupied to prevent others from boarding at the same time.
If multiple passengers arrive at the same time, prioritize the passenger who can board the latest bus.
If no passenger can board the current bus, move to the previous bus and try to fill it.
Continue this process until all buses are considered, and the latest boarding time that is not a passenger's original arrival time is the answer.

Code Implementation

def the_latest_time_to_catch_the_bus(buses, passengers, bus_capacity):
    buses.sort()
    passengers.sort()
    passenger_index = 0
    available_times = set()
    
    for bus_time in buses:
        current_capacity = 0

        # Prioritize passengers who can board later buses.
        for i in range(len(passengers) - 1, -1, -1):
            if passengers[i] <= bus_time and passengers[i] not in available_times and current_capacity < bus_capacity:

                #Try to find a time one second before the passenger's arrival
                time_to_board = passengers[i]
                while time_to_board in available_times:
                    time_to_board -= 1
                    if time_to_board == 0:
                        break

                if time_to_board > 0:
                    available_times.add(time_to_board)
                    current_capacity += 1

    if not available_times:
        return buses[-1]

    latest_possible_time = max(available_times)

    # Ensure the returned time is not a passenger arrival time.
    while latest_possible_time in set(passengers):
        latest_possible_time -= 1

    return latest_possible_time

Big(O) Analysis

Time Complexity

O(n log n) – Sorting the bus arrival times and passenger arrival times both take O(n log n) time where n is the total number of bus and passenger arrival times. Iterating through buses and passengers takes at most O(n*m) time in the worst case where n is the number of buses and m is the number of passengers. Since sorting is the dominant operation, the overall time complexity is O(n log n).

Space Complexity

O(1) – The algorithm sorts the bus arrival times and passenger arrival times in place, thus requiring no additional space proportional to the input size. While the sorting algorithm itself might use some stack space depending on the implementation (e.g., quicksort), the problem description doesn't specify a particular sorting algorithm or constrain us to in-place sorting. The rest of the operations, such as iterating through the sorted arrays and marking times as occupied, use a constant number of variables. Therefore, the overall auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty buses or passengers array	If either array is empty, no passenger can catch a bus, return null/appropriate error value.
buses or passengers array with a single element	Handle the single element array according to the problem rules.
All buses arrive before all passengers	Return the latest time a passenger can arrive before the first bus if possible; otherwise, return the first bus arrival time minus one if there's no earlier valid time.
All passengers arrive before any bus	Return the latest possible arrival time (considering duplicates) before the first bus.
Maximum possible integer value in input	Consider Integer overflow if arrival times are summed up and ensure the result remains within the valid integer range.
Duplicate bus arrival times	The solution should account for duplicate bus arrival times when considering which bus a passenger can take.
Duplicate passenger arrival times	Handle the case where multiple passengers arrive at the same time, ensuring the solution returns the latest possible arrival time.
No passenger can catch any bus	Determine the latest possible time before the first bus arrives if no passenger can catch a bus according to problem constraints; otherwise, there might be an error in input.

Empty buses or passengers array

How to Handle:

If either array is empty, no passenger can catch a bus, return null/appropriate error value.

buses or passengers array with a single element

How to Handle:

Handle the single element array according to the problem rules.

All buses arrive before all passengers

How to Handle:

Return the latest time a passenger can arrive before the first bus if possible; otherwise, return the first bus arrival time minus one if there's no earlier valid time.

All passengers arrive before any bus

How to Handle:

Return the latest possible arrival time (considering duplicates) before the first bus.

Maximum possible integer value in input

How to Handle:

Consider Integer overflow if arrival times are summed up and ensure the result remains within the valid integer range.

Duplicate bus arrival times

How to Handle:

The solution should account for duplicate bus arrival times when considering which bus a passenger can take.

Duplicate passenger arrival times

How to Handle:

Handle the case where multiple passengers arrive at the same time, ensuring the solution returns the latest possible arrival time.

No passenger can catch any bus

How to Handle:

Determine the latest possible time before the first bus arrives if no passenger can catch a bus according to problem constraints; otherwise, there might be an error in input.