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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The Latest Time to Catch a Bus

Number: 2417

Difficulty: Medium

Paid? No

Companies: Microsoft, Google, Zoho, Amazon

Problem Description

Given departure times for a set of buses and arrival times for passengers (all unique), along with a maximum capacity per bus, determine the latest time you can arrive at the bus station (without matching any other passenger’s arrival time) so that you can still catch one of the buses. When a bus departs, it picks up passengers in order of their arrival times (up to its capacity), and you must arrive on or before the bus’s departure time to board it.

Key Insights

  • Sort both the bus departure times and passenger arrival times.
  • For each bus, simulate the boarding process by assigning the earliest arriving passengers until the capacity is reached or there are no more waiting.
  • The target is to determine a time for your arrival such that:
    • If the last bus is not full, you can simply arrive at its departure time (unless that time conflicts with a passenger’s arrival).
    • If the last bus is full, the candidate time shifts to one less than the arrival time of the last passenger who boarded.
  • When choosing your arrival time, ensure it does not match any existing passenger’s arrival time; if it does, decrement until a free time is found.

Space and Time Complexity

Time Complexity: O(n log n + m log m)
Space Complexity: O(1) (ignoring the space required to sort; in-place sorting can be assumed)

Solution

The approach is to simulate the boarding process:

  1. Sort the bus departure times and passengers’ arrival times.
  2. Use a pointer to track which passengers have already been processed.
  3. Iterate through each bus:
    • For each bus, board as many passengers as possible (or until the waiting passengers’ arrival time is too late) by moving the pointer.
  4. For the last bus:
    • If it has not reached capacity, set the candidate arrival time to the bus’s departure time.
    • If the last bus is full, set the candidate time to be one minute before the last boarded passenger’s arrival time.
  5. Since you cannot pick a time that coincides with another passenger's, adjust the candidate time downward if needed until you find a valid time.

The primary data structures used are arrays (which are sorted) and simple pointers iterating through these arrays. The main trick is to properly simulate the boarding and then backtrack from candidate time if it collides with any other passenger arrival.

Code Solutions

# Python solution with detailed comments
def latestTimeCatchTheBus(buses, passengers, capacity):
    # Sort the bus departure times and passenger arrival times.
    buses.sort()
    passengers.sort()

    passenger_index = 0  # pointer for tracking boarding of passengers
    last_boarded = -1  # track the last boarding passenger time on the last bus

    # Process each bus
    for bus_time in buses:
        seats = capacity  # available seats on the current bus
        # Board passengers who can catch the current bus
        while seats > 0 and passenger_index < len(passengers) and passengers[passenger_index] <= bus_time:
            last_boarded = passengers[passenger_index]
            passenger_index += 1
            seats -= 1

    # Determine candidate time based on the last bus
    if seats > 0:
        # If seats are available, candidate is the bus departure time
        candidate = buses[-1]
    else:
        # If the bus is full, candidate is one minute before the last boarded passenger's arrival
        candidate = last_boarded - 1

    # Ensure candidate time doesn't conflict with any passenger's arrival time
    passenger_set = set(passengers)
    while candidate in passenger_set:
        candidate -= 1

    return candidate

# Example usage:
#print(latestTimeCatchTheBus([10,20], [2,17,18,19], 2))  # Expected output: 16
← Back to All Questions