The Latest Time to Catch a Bus solution and explanation
Google
7 more videos on this problem
The Latest Time to Catch a Bus - 2332. LEET CODEWeb Mickey · 20:20 · 2K views
2332. The Latest Time to Catch a Bus (Leetcode Medium)Programming Live with Larry · 21:54 · 1K views
2332. The Latest Time to Catch a Bus | Leetcode | Medium | Java | Greedy AlgorithmAlgorithmHQ · 12:37 · 1K views
【每日一题】LeetCode 2332. The Latest Time to Catch a BusHuifeng Guan · 16:57 · 687 views
Leetcode 2332. The Latest Time to Catch a BusElite Code · 47:02 · 555 views
LEETCODE Weekly Contest 288 | PROBLEM 2331 , 2332, 2333 | GREEDY | BRUTE FORCEcode Explainer · 16:43 · 395 views
LeetCode 2332 The Latest Time to Catch a Bus || C++ Solution || Beginner Friendlyanshumansick · 30:44 · 37 views
【力扣每日一題】Leetcode 2332. 坐上公交的最晚时间 - 1841 Medium - Java - Greedy 貪心、Dual Pointers 雙指針Leetcode刷題最後希望 · 15:27
The 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
capacityor fewer passengers are waiting for a bus, they will all get on the bus, or - The
capacitypassengers 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.lengthm == passengers.length1 <= n, m, capacity <= 1052 <= buses[i], passengers[i] <= 109- Each element in
busesis unique. - Each element in
passengersis unique.
Approach overview
Problem Overview: You are given departure times of buses, arrival times of passengers, and a capacity for each bus. Passengers board the earliest bus they can catch until capacity is full. The task is to determine the latest possible time you can arrive at the station and still board a bus, while ensuring your arrival time does not match any existing passenger time.
Approach 1: Sorted Two-Pointer Simulation (O(n log n + m log m) time, O(1) extra space)
Sort both the buses and passengers arrays. Then simulate the boarding process using two pointers. Iterate through buses in chronological order and greedily assign passengers who arrive before or at the bus departure until the bus reaches capacity. After processing the last bus, determine the latest valid arrival time: if the bus still has space, you can arrive exactly at its departure; if it is full, the candidate time becomes one minute before the last boarded passenger. Decrease the time while it conflicts with existing passenger arrival times. The technique relies on sorted traversal and pointer advancement, a common pattern in Two Pointers and Array problems.
Approach 2: Greedy Backtrack with Binary Search (O((n + m) log m) time, O(1) space)
Another strategy treats the answer as a search problem. First sort buses and passengers. Use Binary Search to test candidate arrival times. For each candidate time, simulate whether boarding is possible by greedily assigning passengers to buses while including the hypothetical arrival. If the candidate time allows boarding, move the search window later; otherwise move earlier. After finding the latest feasible time, backtrack if that timestamp coincides with an existing passenger arrival. This approach separates feasibility checking from answer discovery, which can be useful when constraints grow or the boarding rule becomes more complex.
Recommended for interviews: The sorted two-pointer simulation is the expected solution. It directly models the boarding process and runs in O(n log n + m log m) due to sorting. Interviewers prefer this approach because the logic is transparent and easy to reason about. The binary-search variant shows deeper algorithmic thinking but adds unnecessary complexity for this specific problem.
Approach 1: Sorted Two-Pointer Approach
To solve this problem, we employ a two-pointer technique after sorting both the buses and passengers arrays. The bus with the latest departure time will determine your latest possible arrival time.
Throughout, we'll track which passengers can board each bus until no more passengers can fit or there are no waiting passengers. Eventually, check when you can arrive just before the last passenger eligible for the last bus.
def latestTimeToCatchBus(buses, passengers, capacity):
buses.sort()
passengers.sort()
p_idx = 0
num_passengers = len(passengers)
for bus in buses:
count = 0
while p_idx < num_passengers and passengers[p_idx] <= bus and count < capacity:
count += 1
p_idx += 1
latest_time = bus if count < capacity else passengers[p_idx-1] - 1
while latest_time in set(passengers):
latest_time -= 1
return latest_timeimport java.util.Arrays;
public class Solution {
public int latestTimeToCatchBus(int[] buses, int[] passengers, int capacity) {
Arrays.sort(buses);
Arrays.sort(passengers);
int pIdx = 0;
for (int bus : buses) {
int count = 0;
while (pIdx < passengers.length && passengers[pIdx] <= bus && count < capacity) {
count++;
pIdx++;
}
}
int latestTime = buses[buses.length - 1];
if (pIdx > 0 && passengers[pIdx - 1] < buses[buses.length - 1] && pIdx <= passengers.length) {
latestTime = passengers[pIdx - 1] - 1;
}
while (Arrays.binarySearch(passengers, latestTime) >= 0) {
latestTime--;
}
return latestTime;
}
}function latestTimeToCatchBus(buses, passengers, capacity) {
buses.sort((a, b) => a - b);
passengers.sort((a, b) => a - b);
let pIdx = 0;
for (let bus of buses) {
let count = 0;
while (pIdx < passengers.length && passengers[pIdx] <= bus && count < capacity) {
count++;
pIdx++;
}
}
let latestTime = buses[buses.length-1];
if (pIdx > 0 && passengers[pIdx - 1] < latestTime && (pIdx < passengers.length || count < capacity)) {
latestTime = passengers[pIdx - 1] - 1;
}
while (passengers.includes(latestTime)) {
latestTime--;
}
return latestTime;
}Sort the buses and passengers. For each bus, assign passengers whose arrival is before or equal to the departure, counting how many board. Adjust the potential arrival time backward until a free slot is found.
Time Complexity: O((n + m) log(n + m)) due to sorting.
Space Complexity: O(1) for in-place operations.
Approach 2: Greedy Backtrack Approach with Binary Search
This method determines the latest optimal time to arrive by initially supposing you arrive at the bus's latest possible time, backtracking from there while enforcing the unique arrival constraint. By leveraging binary search over the passenger list, we assure minimal comparison operations.
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
int latestTimeToCatchBus(std::vector<int>& buses, std::vector<int>& passengers, int capacity) {
std::sort(buses.begin(), buses.end());
std::sort(passengers.begin(), passengers.end());
int pIdx = 0;
for (int i = 0; i < buses.size(); i++) {
int count = 0;
while (pIdx < passengers.size() && passengers[pIdx] <= buses[i] && count < capacity) {
count++;
pIdx++;
}
}
int latestTime = buses.back();
if (pIdx > 0 && passengers[pIdx - 1] < latestTime && (pIdx < passengers.size() || count < capacity)) {
latestTime = passengers[pIdx - 1] - 1;
}
std::set<int> passengerSet(passengers.begin(), passengers.end());
while (passengerSet.find(latestTime) != passengerSet.end()) {
latestTime--;
}
return latestTime;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int latestTimeToCatchBus(int* buses, int n, int* passengers, int m, int capacity) {
qsort(buses, n, sizeof(int), compare);
qsort(passengers, m, sizeof(int), compare);
int pIdx = 0;
for (int i = 0; i < n; ++i) {
int count = 0;
while (pIdx < m && passengers[pIdx] <= buses[i] && count < capacity) {
count++;
pIdx++;
}
}
int lastPos = buses[n-1];
if (pIdx == 0 || passengers[pIdx-1] != lastPos || (pIdx < m && passengers[pIdx] != lastPos)) {
lastPos = passengers[pIdx-1] - 1;
}
int is_passenger_present;
do {
is_passenger_present = 0;
for (int i = 0; i < m; ++i) {
if (passengers[i] == lastPos) {
is_passenger_present = 1;
lastPos--;
break;
}
}
} while (is_passenger_present);
return lastPos;
}Sort both buses and passengers vectors, and use a set to efficiently check unwanted times. Then work backwards from conceivable slots until reaching one unmet by current passengers.
Time Complexity: O((n + m) log(n + m))
Space Complexity: O(n) due to set storage.
Approach 3: Simulation
First, we sort, and then use double pointers to simulate the process of passengers getting on the bus: traverse the bus bus, passengers follow the principle of "first come, first served".
After the simulation ends, judge whether the last bus still has seats:
- If there are seats, we can arrive at the bus station when the bus departs at
bus[|bus|-1]; if there are people at this time, we can find the time when no one arrives by going forward. - If there are no seats, we can find the last passenger who got on the bus, and find the time when no one arrives by going forward from him.
The time complexity is O(n times log n + m times log m), and the space complexity is O(log n + log m). Where n and m are the numbers of buses and passengers respectively.
function latestTimeCatchTheBus(buses: number[], passengers: number[], capacity: number): number {
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;
}func latestTimeCatchTheBus(buses []int, passengers []int, capacity int) int {
sort.Ints(buses)
sort.Ints(passengers)
j, c := 0, 0
for _, t := range buses {
c = capacity
for c > 0 && j < len(passengers) && passengers[j] <= t {
j++
c--
}
}
j--
ans := buses[len(buses)-1]
if c == 0 {
ans = passengers[j]
}
for j >= 0 && ans == passengers[j] {
ans--
j--
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorted Two-Pointer Approach | Time Complexity: O((n + m) log(n + m)) due to sorting. |
| Greedy Backtrack Approach with Binary Search | Time Complexity: O((n + m) log(n + m)) |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorted Two-Pointer Simulation | O(n log n + m log m) | O(1) | Best general solution. Efficient when buses and passengers can be sorted and simulated sequentially. |
| Greedy Backtrack with Binary Search | O((n + m) log m) | O(1) | Useful when treating the answer as a search space or when feasibility checks are easier than direct computation. |
Frequently asked questions
Is The Latest Time to Catch a Bus easy or hard?
The problem is rated Medium because the logic requires careful simulation and handling of edge cases such as full buses and duplicate passenger arrival times. The algorithm itself is straightforward once you recognize that sorting and greedy boarding lead to the correct answer.
The Latest Time to Catch a Bus Python/Java solution
Typical implementations sort the buses and passengers arrays, then simulate boarding with two pointers. Python, Java, and JavaScript versions usually follow the same greedy structure: iterate buses, board passengers until capacity, and compute the latest safe arrival time that does not match existing passenger timestamps.
How to solve The Latest Time to Catch a Bus in O(n)?
An exact O(n) solution is generally not possible because the passenger and bus schedules must be processed in chronological order. Sorting both arrays is required unless the inputs are already sorted. Once sorted, the boarding simulation itself runs in linear O(n + m) time using two pointers.
What is the best approach for The Latest Time to Catch a Bus?
The sorted two-pointer simulation is the most practical solution. Sort buses and passengers, then simulate the boarding process while tracking capacity. After the last bus is processed, compute the latest valid arrival time that does not conflict with existing passengers. This approach runs in O(n log n + m log m) time due to sorting.
Is The Latest Time to Catch a Bus asked at Google/Amazon/Meta?
This problem represents a common scheduling and simulation pattern frequently used in technical interviews at companies like Amazon, Google, and Meta. Variants involving resource allocation, queues, and greedy boarding logic appear regularly in interview rounds.
What data structure is used in The Latest Time to Catch a Bus?
The solution primarily uses arrays with sorting and a two-pointer traversal. No complex data structures are required. Some implementations also use sets or pointer checks to avoid choosing a time that already exists in the passenger list.
What is the time complexity of The Latest Time to Catch a Bus?
The optimal approach runs in O(n log n + m log m) time where n is the number of buses and m is the number of passengers. The complexity comes from sorting both arrays. The actual boarding simulation uses a linear two-pointer scan with O(n + m) time and O(1) additional space.