The Latest Time to Catch a Bus Solution in Python

Links to Other Solutions

Code Solution


class Solution:
    def latestTimeCatchTheBus(
        self,
        buses: list[int],
        passengers: list[int],
        capacity: int,
    ) -> int:
        buses.sort()
        passengers.sort()

        if passengers[0] > buses[-1]:
            return buses[-1]

        ans = passengers[0] - 1
        i = 0  # buses' index
        j = 0  # passengers' index

        while i < len(buses):
            arrived = 0
            while arrived < capacity and j < len(passengers) and passengers[j] <= buses[i]:
                if j > 0 and passengers[j] != passengers[j - 1] + 1:
                    ans = passengers[j] - 1
                j += 1
                arrived += 1
            if arrived < capacity and j > 0 and passengers[j - 1] != buses[i]:
                ans = buses[i]
            i += 1

        return ans

Problem Description

Ah, the classic dilemma of catching a bus! You know, that moment when you’re sprinting like an Olympic athlete, only to see the bus doors close right in front of you. The problem, “The Latest Time to Catch a Bus,” is a delightful little puzzle that asks you to determine the latest time you can arrive at the bus stop and still catch your ride.

Imagine this: you have a list of buses leaving at specific times and a list of passengers arriving at the bus stop. Each bus has a limited capacity, and you want to maximize your chances of getting on board. But wait! You can’t just waltz in at any time; you need to be strategic.

So, how do you figure out the latest time you can arrive without missing the bus? It’s like trying to sneak into a party after the bouncer has already checked the guest list. Spoiler alert: it’s not easy!

Approach Explanation

The solution employs a greedy algorithm. First, it sorts both the bus and passenger lists. Then, it iterates through the buses, checking how many passengers can board each bus based on its capacity. If there’s room for one more passenger, it updates the latest possible arrival time. The goal is to find the latest time you can arrive at the bus stop without missing your ride.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n + m log m)
Space Complexity	O(1)

Real-World Example

Picture this: You’re at a bus stop, and the bus is scheduled to leave at 5:00 PM. You arrive at 4:59 PM, but the bus is already full. You think, “If only I had arrived a minute earlier!” This problem encapsulates that very scenario, allowing you to calculate the latest time you could have arrived to ensure you catch the bus.