Problem Description

You have n buses and m passengers. Each bus departs at a specific time given in the array buses[i], and each passenger arrives at a specific time given in the array passengers[j]. All departure times are unique, and all arrival times are unique.

Each bus can hold at most capacity passengers. When passengers arrive at the bus station, they wait in line for the next available bus. A passenger can board a bus that departs at time x if they arrive at time y where y <= x, and the bus still has available seats.

The boarding process follows these rules:

• Passengers board in the order of their arrival times (earliest arrivals board first)
• When a bus arrives:
  • If the number of waiting passengers is less than or equal to capacity, all waiting passengers board
  • Otherwise, only the capacity passengers with the earliest arrival times board

Your task is to find the latest possible time you can arrive at the bus station and still catch a bus. You cannot arrive at the same time as any other passenger.

The solution simulates the boarding process by sorting both arrays and using two pointers. It tracks which passengers board each bus based on their arrival times and the bus capacity. After simulation, it determines the latest arrival time by checking if the last bus has remaining capacity. If it does, you can arrive when the last bus departs (adjusting backwards if that time conflicts with another passenger). If not, you need to arrive just before the last passenger who boarded, finding a time slot where no other passenger arrives.

Intuition

To find the latest time we can arrive and still catch a bus, we need to understand when the last opportunity to board occurs. This depends on two factors: which buses still have space and which time slots are available (not taken by other passengers).

The key insight is that we want to arrive as late as possible, so we should aim for the last bus if possible. But we can't just arrive when the last bus departs - we need to check if there's actually space on it.

To determine available spaces, we must simulate the entire boarding process. By sorting both arrays and processing them chronologically, we can track exactly which passengers board which buses. We iterate through each bus and let passengers board in arrival order until either the bus is full or no more eligible passengers remain.

After simulation, we face two scenarios:

1. The last bus has empty seats: We could potentially arrive when this bus departs (at buses[-1]). However, if another passenger already arrives at that exact time, we need to arrive one minute earlier. We keep checking backwards until we find a time no passenger occupies.

2. The last bus is full: We can't board the last bus arriving at its departure time. Our best chance is to "squeeze in" before the last passenger who successfully boarded. Starting from their arrival time minus one, we search backwards for an available time slot.

The backwards search for an available time slot is crucial because multiple passengers might arrive consecutively (e.g., at times 4, 5, 6). We need to find a gap in these arrival times or arrive even earlier if necessary.

This greedy approach works because arriving later is always better than arriving earlier (as long as we can still board a bus), and we systematically find the latest feasible arrival time by working backwards from the theoretical maximum.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation follows a simulation strategy with careful tracking of passenger boarding:

Step 1: Sort both arrays

buses.sort()
passengers.sort()

Sorting allows us to process events chronologically and ensures passengers board in arrival order.

Step 2: Simulate the boarding process

j = 0
for t in buses:
    c = capacity
    while c and j < len(passengers) and passengers[j] <= t:
        c, j = c - 1, j + 1

• Initialize pointer j to track the next passenger in line
• For each bus departing at time t:
  • Set available seats c = capacity
  • While there are seats (c > 0), more passengers to process (j < len(passengers)), and the next passenger arrived before or at bus departure (passengers[j] <= t):
    • Board the passenger: decrease capacity c - 1 and move to next passenger j + 1
• After the loop, j points to the first passenger who couldn't board any bus

Step 3: Determine the latest arrival time

j -= 1
ans = buses[-1] if c else passengers[j]

• Move j back to point to the last passenger who boarded (j -= 1)
• If the last bus has remaining capacity (c > 0), we can potentially arrive at the last bus's departure time buses[-1]
• Otherwise, we start from the last boarded passenger's time passengers[j] to find an earlier slot

Step 4: Find an available time slot

while ~j and passengers[j] == ans:
    ans, j = ans - 1, j - 1

• The condition ~j is equivalent to j >= 0 (bitwise NOT of -1 is 0)
• While we haven't checked all passengers and current time ans conflicts with a passenger's arrival:
  • Move to one minute earlier (ans - 1)
  • Check the previous passenger (j - 1)
• This loop finds the latest time that doesn't conflict with any passenger's arrival

The algorithm efficiently combines sorting, two-pointer technique, and backwards searching to find the optimal arrival time in O(n log n + m log m) time complexity, where n is the number of buses and m is the number of passengers.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input:

• buses = [10, 20] (2 buses departing at times 10 and 20)
• passengers = [2, 17, 18, 19] (4 passengers arriving at these times)
• capacity = 2 (each bus can hold 2 passengers)

Step 1: Sort arrays (already sorted in this example)

• buses = [10, 20]
• passengers = [2, 17, 18, 19]

Step 2: Simulate boarding process

Initialize j = 0 (pointing to first passenger)

Processing Bus 1 (departs at time 10):

• Available seats c = 2
• Check passenger at index 0 (arrives at time 2): 2 <= 10 ✓ → Board!
  • Update: c = 1, j = 1
• Check passenger at index 1 (arrives at time 17): 17 <= 10 ✗ → Cannot board
• Bus 1 departs with 1 passenger, 1 empty seat remains

Processing Bus 2 (departs at time 20):

• Available seats c = 2
• Check passenger at index 1 (arrives at time 17): 17 <= 20 ✓ → Board!
  • Update: c = 1, j = 2
• Check passenger at index 2 (arrives at time 18): 18 <= 20 ✓ → Board!
  • Update: c = 0, j = 3
• Check passenger at index 3 (arrives at time 19): 19 <= 20 ✓ but c = 0 → No seats left!
• Bus 2 departs full with passengers who arrived at times 17 and 18

After simulation: j = 3, c = 0 (last bus is full)

Step 3: Determine latest arrival time

• j = 3 - 1 = 2 (index of last passenger who boarded)
• Since c = 0 (last bus full), we start from passengers[2] = 18
• Set ans = 18

Step 4: Find available time slot

• Check if time 18 conflicts: passengers[2] = 18 equals ans = 18 ✓ Conflict!
  • Update: ans = 17, j = 1
• Check if time 17 conflicts: passengers[1] = 17 equals ans = 17 ✓ Conflict!
  • Update: ans = 16, j = 0
• Check if time 16 conflicts: passengers[0] = 2 does not equal ans = 16 ✗ No conflict!

Result: The latest you can arrive is at time 16. You would board Bus 2 along with passengers arriving at times 17 and 18.

This example demonstrates why we can't simply arrive when the last bus departs (time 20) - it's already full! Instead, we must arrive early enough to secure a spot before other passengers, finding the latest time (16) that doesn't conflict with existing passenger arrivals.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n + m × log m)

The time complexity is dominated by two sorting operations:

• buses.sort() takes O(n × log n) time where n is the number of buses
• passengers.sort() takes O(m × log m) time where m is the number of passengers
• The first for loop iterates through all buses (n iterations), and the inner while loop processes each passenger at most once across all iterations, contributing O(n + m) time
• The final while loop in the worst case iterates through all passengers once, contributing O(m) time
• Overall: O(n × log n + m × log m + n + m) = O(n × log n + m × log m)

Space Complexity: O(log n + log m)

The space complexity comes from:

• The sorting operations use O(log n) space for sorting buses (typical for in-place sorting algorithms like Timsort used in Python)
• The sorting operations use O(log m) space for sorting passengers
• Only a constant amount of additional variables are used (j, c, ans, t)
• Overall: O(log n + log m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Capacity Tracking Across Buses

A critical mistake is not resetting the capacity variable for each bus. The variable current_capacity gets overwritten in each bus iteration, but after the loop ends, it only reflects the remaining capacity of the last bus, not any arbitrary bus.

Incorrect approach:

# Wrong: Using a single capacity variable without proper tracking
capacity_left = capacity
for bus_time in buses:
    # Process passengers...
    capacity_left -= passengers_boarded  # This loses information about previous buses

Solution: The code correctly handles this by reassigning current_capacity = capacity at the start of each bus iteration, and the final value of current_capacity specifically represents the last bus's remaining capacity, which is what we need.

2. Off-by-One Error When Finding Non-Conflicting Time

When searching backwards for an available time slot, forgetting to decrement the passenger index can cause an infinite loop or incorrect result.

Incorrect approach:

# Wrong: Not moving the passenger pointer backwards
while passenger_index >= 0 and passengers[passenger_index] == latest_time:
    latest_time -= 1
    # Missing: passenger_index -= 1

Solution: Always decrement both the time and passenger index together to properly check all conflicting times in reverse order.

3. Misunderstanding the Final Passenger Index

After the simulation loop, passenger_index points to the first passenger who couldn't board. A common mistake is using this index directly without adjusting it.

Incorrect approach:

# Wrong: Using passenger_index without adjustment
if current_capacity > 0:
    latest_time = buses[-1]
else:
    latest_time = passengers[passenger_index]  # Wrong! This passenger didn't board

Solution: Always decrement passenger_index by 1 after the simulation to point to the last passenger who actually boarded: passenger_index -= 1

4. Not Handling Edge Cases with Empty Passengers Array

If there are no passengers or very few passengers compared to total bus capacity, the passenger_index could become negative, causing index out of bounds errors.

Solution: The code handles this elegantly by checking passenger_index >= 0 in the final while loop (or using ~j which becomes False when j is -1). This prevents accessing invalid indices when working backwards through the passenger array.