The Latest Time to Catch a Bus Solution in Java

Links to Other Solutions

Code Solution


class Solution {
  public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
    Arrays.sort(buses);
    Arrays.sort(passengers);

    if (passengers[0] > buses[buses.length - 1])
      return buses[buses.length - 1];

    int ans = passengers[0] - 1;
    int i = 0; // buses' index
    int j = 0; // passengers' index

    while (i < buses.length) {
      int arrived = 0;
      while (arrived < capacity && j < passengers.length && passengers[j] <= buses[i]) {
        if (j > 0 && passengers[j] != passengers[j - 1] + 1)
          ans = passengers[j] - 1;
        ++j;
        ++arrived;
      }
      if (arrived < capacity && j > 0 && passengers[j - 1] != buses[i])
        ans = buses[i];
      ++i;
    }

    return ans;
  }
}

Problem Description

Ah, the classic dilemma of catching the 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 at hand is all about timing—specifically, figuring out the latest time you can arrive at the bus stop without missing your ride.

Imagine you’re at a bus stop, and there are a few buses scheduled to arrive. You also have a group of passengers who are just as eager to catch those buses. Each bus has a limited capacity, and you need to determine the latest time you can arrive at the bus stop to ensure you can still catch a bus.

In simpler terms, if you’re late, you might as well start walking, because the bus isn’t waiting for you!

Approach Explanation

The solution employs a greedy algorithm. First, it sorts the buses and passengers to ensure we can efficiently determine who catches which bus. The algorithm iterates through each bus, checking how many passengers can board based on the bus’s capacity. If there’s room for one more passenger, it checks if that passenger can arrive at the bus stop just in time. The goal is to maximize the latest time you can arrive without missing the bus.

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 concert, and the last bus is about to leave. You know that if you miss it, you’ll be stuck waiting for an hour for the next one. You check your watch and realize you have just a few minutes left. You need to calculate the latest time you can leave your spot in the crowd to catch that bus. This problem is essentially about making sure you don’t miss that bus, just like you wouldn’t want to miss the encore performance of your favorite band!