We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

The Latest Time to Catch a Bus

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array buses of length n, where buses[i] represents the departure time of the ith bus. You are also given a 0-indexed integer array passengers of length m, where passengers[j] represents the arrival time of the jth 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.

Key Insights

  • Buses have unique departure times, and passengers have unique arrival times.
  • Passengers must arrive before the bus departs to catch it.
  • The bus can only take a limited number of passengers, defined by its capacity.
  • We need to find the latest possible time to arrive at the bus station without coinciding with any passenger's arrival time.

Space and Time Complexity

Time Complexity: O(n log n + m log m), where n is the number of buses and m is the number of passengers. The sorting of both arrays dominates the complexity.

Space Complexity: O(m), primarily for storing sorted passenger arrival times.

Solution

To solve this problem, we can use the following approach:

  1. Sort the buses and passengers arrays.
  2. Iterate through each bus, and for each bus, determine how many passengers can board based on their arrival times and the bus's capacity.
  3. Keep track of the time when the last passenger boards the bus, and ensure that our arrival time does not coincide with any passenger's arrival.

We will use sorting and a two-pointer technique to efficiently determine the latest time we can arrive to catch a bus.

Code Solutions

def latestTimeToCatchBus(buses, passengers, capacity):
    buses.sort()  # Sort bus departure times
    passengers.sort()  # Sort passenger arrival times
    passenger_index = 0  # Pointer for passengers
    n = len(buses)
    
    for bus in buses:
        count = 0  # Count of passengers that board this bus
        while passenger_index < len(passengers) and passengers[passenger_index] <= bus and count < capacity:
            count += 1
            passenger_index += 1
            
    # Determine the latest time to arrive
    latest_time = buses[-1]  # Start with the last bus time
    if count == capacity:
        latest_time = passengers[passenger_index - 1] - 1  # Adjust if last bus is full
    
    # Ensure we do not arrive at the same time as any passenger
    while latest_time in passengers:
        latest_time -= 1
        
    return latest_time
← Back to All Questions