# The Latest Time to Catch a Bus
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/the-latest-time-to-catch-a-bus)
Canonical: https://scaleengineer.com/dsa/problems/the-latest-time-to-catch-a-bus
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Zoho](https://scaleengineer.com/companies/zoho)
---
## Problem
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.

**Note:** The arrays `buses` and `passengers` are not necessarily sorted.

**Example 1:**

**Input:** buses = [10,20], passengers = [2,17,18,19], capacity = 2
**Output:** 16
**Explanation:** Suppose you arrive at time 16.
At time 10, the first bus departs with the 0th passenger. 
At time 20, the second bus departs with you and the 1st passenger.
Note that you may not arrive at the same time as another passenger, which is why you must arrive before the 1st passenger to catch the bus.

**Example 2:**

**Input:** buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
**Output:** 20
**Explanation:** Suppose you arrive at time 20.
At time 10, the first bus departs with the 3rd passenger. 
At time 20, the second bus departs with the 5th and 1st passengers.
At time 30, the third bus departs with the 0th passenger and you.
Notice if you had arrived any later, then the 6th passenger would have taken your seat on the third bus.

**Constraints:**

* `n == buses.length`
* `m == passengers.length`
* `1 <= n, m, capacity <= 105`
* `2 <= buses[i], passengers[i] <= 109`
* Each element in `buses` is **unique**.
* Each element in `passengers` is **unique**.

# Approaches
## Brute-Force Simulation on Candidate Times
This approach considers all plausible arrival times and tests each one. The plausible times are derived from the bus departure times and passenger arrival times. We generate a set of candidate times, such as `buses[i]` and `passengers[j] - 1`. Then, for each candidate time, starting from the latest, we run a full simulation to check if arriving at that time would allow us to catch a bus. The first (i.e., latest) candidate time that works is our answer.
**Time:** O((n+m) * m log m), where `n` is the number of buses and `m` is the number of passengers. Generating and sorting `O(n+m)` candidates takes `O((n+m)log(n+m))`. For each candidate, we perform a simulation which involves sorting `m+1` passengers (`O(m log m)`) and then iterating through buses and passengers (`O(n+m)`). This makes the overall complexity dominated by the simulation loop. · **Space:** O(n + m) to store the candidate times and the temporary passenger list for simulations.
**Pros:** Conceptually straightforward, breaking the problem down into generation and testing phases.
**Cons:** Extremely inefficient due to the repeated simulations for each candidate time.; The complexity of `O((n+m) * m log m)` makes it infeasible for the given constraints, leading to a 'Time Limit Exceeded' error.
### Explanation
The core idea is to test potential answers from latest to earliest. The potential answers (candidates) are logically derived from the input times. For any candidate time `t`, we check its validity by simulating the entire scenario with our arrival time included.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    // Helper function to check if arriving at myTime lets us catch a bus.
    private boolean canCatchBus(int[] buses, int[] passengers, int capacity, int myTime) {
        List<Integer> allPassengers = new ArrayList<>();
        for (int p : passengers) {
            allPassengers.add(p);
        }
        allPassengers.add(myTime);
        Collections.sort(allPassengers);

        int pIdx = 0;
        boolean caughtBus = false;

        for (int busTime : buses) {
            int boarded = 0;
            while (pIdx < allPassengers.size() && allPassengers.get(pIdx) <= busTime && boarded < capacity) {
                if (allPassengers.get(pIdx) == myTime) {
                    caughtBus = true;
                }
                pIdx++;
                boarded++;
            }
        }
        return caughtBus;
    }

    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        
        Set<Integer> passengerSet = new HashSet<>();
        for (int p : passengers) {
            passengerSet.add(p);
        }

        Set<Integer> candidates = new HashSet<>();
        for (int b : buses) {
            candidates.add(b);
        }
        for (int p : passengers) {
            candidates.add(p - 1);
        }

        List<Integer> sortedCandidates = new ArrayList<>(candidates);
        Collections.sort(sortedCandidates, Collections.reverseOrder());

        for (int t : sortedCandidates) {
            if (t <= 0 || passengerSet.contains(t)) {
                continue;
            }
            if (canCatchBus(buses, passengers, capacity, t)) {
                return t;
            }
        }
        
        return -1; // Should not be reached given problem constraints.
    }
}
```
### Algorithm
- Generate a set of all plausible candidate arrival times. A good set of candidates includes all bus departure times (`buses[i]`) and times just before each passenger arrives (`passengers[j] - 1`).
- Sort the unique candidate times in descending order.
- For each candidate time `t`, check if it's a valid arrival time for us:
  - The time `t` must not be taken by another passenger.
  - We must be able to board a bus if we arrive at time `t`.
- To check if we can board a bus, perform a full simulation:
  - Add our arrival time `t` to the list of passengers.
  - Re-sort the combined list of passengers.
  - Simulate the entire boarding process using a two-pointer approach for buses and the new passenger list.
  - If our arrival time `t` is among those who successfully board a bus, then `t` is a valid time.
- The first valid time found (since we are iterating from latest to earliest) is the answer.

## Optimized Simulation with Two Pointers and HashSet
A much more efficient approach is to simulate the entire process just once and then deduce the answer from the final state. By sorting both the `buses` and `passengers` arrays, we can use a two-pointer technique to efficiently simulate which passengers board which bus. After the simulation, we only need to consider the last bus. If it has space, we can arrive at its departure time. If it's full, we must arrive before the last person who boarded it. Finally, we adjust this time downwards to ensure it's unique and not taken by another passenger.
**Time:** O(n log n + m log m). Sorting the arrays takes `O(n log n + m log m)`. Building the `HashSet` takes `O(m)`. The simulation itself is a single pass through both arrays, taking `O(n + m)`. The final `while` loop to find a unique time can take up to `O(m)` in the worst case. The overall complexity is dominated by the initial sorting. · **Space:** O(m) to store the `HashSet` of passenger arrival times. The space for sorting is typically `O(log n + log m)` or `O(n+m)` depending on the implementation.
**Pros:** Highly efficient with a time complexity dominated by sorting.; Solves the problem in a single pass after sorting, avoiding redundant computations.; Correctly handles all constraints and edge cases.
**Cons:** Requires careful handling of pointers and edge cases, such as when no passengers can board any bus.; Uses extra space for the HashSet, which could be significant if the number of passengers is very large.
### Explanation
This optimized approach avoids re-computation by performing a single pass after sorting. The key is realizing that our latest possible arrival time is determined by the conditions of the last bus.

Here is the implementation in Java:
```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        // Sort both arrays to process chronologically.
        Arrays.sort(buses);
        Arrays.sort(passengers);

        // Use a HashSet for O(1) lookups of passenger arrival times.
        Set<Integer> passengerSet = new HashSet<>();
        for (int p : passengers) {
            passengerSet.add(p);
        }

        int passengerIdx = 0;
        int capacityLeft = 0;

        // Simulate the boarding process for all buses.
        for (int busTime : buses) {
            capacityLeft = capacity;
            while (passengerIdx < passengers.length && passengers[passengerIdx] <= busTime && capacityLeft > 0) {
                passengerIdx++;
                capacityLeft--;
            }
        }

        int latestTime;
        // Determine the candidate latest time based on the last bus's state.
        if (capacityLeft > 0) {
            // The last bus had space. We can aim to arrive at the bus departure time.
            latestTime = buses[buses.length - 1];
        } else {
            // The last bus was full. The last passenger to board was at index passengerIdx - 1.
            // We need to take their spot, so we must arrive at or before their time.
            latestTime = passengers[passengerIdx - 1];
        }

        // Adjust the time to be unique. Decrement until we find a time slot not taken.
        while (passengerSet.contains(latestTime)) {
            latestTime--;
        }

        return latestTime;
    }
}
```
### Algorithm
- First, sort both the `buses` and `passengers` arrays. This allows us to process them in chronological order.
- Create a `HashSet` of passenger arrival times for O(1) average time complexity lookups to check for time conflicts.
- Simulate the passenger boarding process once. Use a pointer for buses and another for passengers. Iterate through each bus, and for each bus, board the waiting passengers (those whose arrival time is less than or equal to the bus departure time) until the bus is full or there are no more eligible passengers.
- After the simulation loop finishes, analyze the state of the last bus:
  - If the last bus had remaining capacity, it means we could have boarded it. The latest we could arrive is its departure time, `buses[n-1]`.
  - If the last bus was full, the last passenger to board was `passengers[passenger_idx - 1]`. To take their spot, we must arrive at or before their time. So, our candidate time is `passengers[passenger_idx - 1]`.
- Let the time determined in the previous step be `latest_time`.
- Since we cannot arrive at the same time as another passenger, we must find the latest time `t <= latest_time` that is not in the passenger arrival `HashSet`. We can do this by repeatedly decrementing `latest_time` while it's present in the set.
- The final value of `latest_time` is the answer.

# Solutions
### Java

```java
class Solution {
public
  int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
    Arrays.sort(buses);
    Arrays.sort(passengers);
    int j = 0, c = 0;
    for (int t : buses) {
      c = capacity;
      while (c > 0 && j < passengers.length && passengers[j] <= t) {
        --c;
        ++j;
      }
    }
    --j;
    int ans = c > 0 ? buses[buses.length - 1] : passengers[j];
    while (j >= 0 && ans == passengers[j]) {
      --ans;
      --j;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} buses * @param {number[]} passengers * @param {number} capacity * @return {number} */ var latestTimeCatchTheBus =
  function (buses, passengers, capacity) {
    buses.sort((a, b) => a - b);
    passengers.sort((a, b) => a - b);
    let [j, c] = [0, 0];
    for (const t of buses) {
      c = capacity;
      while (c && j < passengers.length && passengers[j] <= t) {
        --c;
        ++j;
      }
    }
    --j;
    let ans = c > 0 ? buses.at(-1) : passengers[j];
    while (j >= 0 && passengers[j] === ans) {
      --ans;
      --j;
    }
    return ans;
  };

```

### CPP

```cpp
class Solution { public: int latestTimeCatchTheBus ( vector < int >& buses , vector < int >& passengers , int capacity ) { sort ( buses . begin (), buses . end ()); sort ( passengers . begin (), passengers . end ()); int j = 0 , c = 0 ; for ( int t : buses ) { c = capacity ; while ( c && j < passengers . size () && passengers [ j ] <= t ) -- c , ++ j ; } -- j ; int ans = c ? buses [ buses . size () - 1 ] : passengers [ j ]; while ( ~ j && ans == passengers [ j ]) -- j , -- ans ; return ans ; } };
```

### Python

```python
class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int: buses . sort() passengers . sort() j = 0 for t in buses: c = capacity while c and j < len(passengers) and passengers[j] <= t: c, j = c - 1, j + 1 j -= 1 ans = buses[- 1] if c else passengers[j] while ~ j and passengers[j] == ans: ans, j = ans - 1, j - 1 return ans

```