The Latest Time to Catch a Bus - Practice Coding Problems

The Latest Time to Catch a Bus - Problem

You are given a 0-indexed integer array buses of length n, where buses[i] represents the departure time of the i^th bus. You are also given a 0-indexed integer array passengers of length m, where passengers[j] represents the arrival time of the j^th 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.

Input & Output

Example 1 — Basic Case

$ Input: buses = [10,20], passengers = [2,17,18,19], capacity = 2

› Output: 16

💡 Note: Bus 10: passengers 2 boards. Bus 20: passengers 17,18 board (full). We can arrive at 16, displace passenger 17, and catch bus 20.

Example 2 — Space Available

$ Input: buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2

› Output: 20

💡 Note: After sorting: Bus 10 takes [4,11], Bus 20 takes [13,19], Bus 30 takes [21,25]. Bus 20 has space, so we can arrive exactly at time 20 (but 19 conflicts, so 18).

Example 3 — Single Bus

$ Input: buses = [3], passengers = [2], capacity = 2

› Output: 3

💡 Note: Bus 3 takes passenger 2 and has space for 1 more. We can arrive at time 3 and catch the bus.

Constraints

n == buses.length
m == passengers.length
1 ≤ n, m, capacity ≤ 10⁵
2 ≤ buses[i], passengers[i] ≤ 10⁹
Each element in buses is unique
Each element in passengers is unique

Visualization

Tap to expand

Understanding the Visualization

Input

Buses [10,20], Passengers [2,17,18,19], Capacity 2

Simulate

Bus 10: passenger 2 boards, Bus 20: passengers 17,18 board

Optimize

Arrive at 16 to displace passenger 17 and catch bus 20

Key Takeaway

🎯 Key Insight: Either arrive at the bus departure time if there's space, or arrive just before another passenger to displace them

Asked in

M Microsoft 15 G Google 12 a Amazon 8 f Meta 6

The key insight is to sort times, simulate boarding, then work backwards from the last bus. Either arrive at the bus departure time (if space available) or displace the latest passenger. Best approach is Sort and Simulate. Time: O((N+M) log (N+M)), Space: O(N+M)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try Every Time	O(T×(N+M))	O(M)	Try every possible arrival time from latest to earliest
Sort and Simulate	O((N+M) log (N+M))	O(N+M)	Sort buses and passengers, simulate boarding, find optimal arrival time

Brute Force - Try Every Time — Algorithm Steps

Step 1: Try arrival times from latest bus time down to 1
Step 2: For each time, simulate all passengers boarding buses
Step 3: Check if we can board any bus with our arrival time
Step 4: Return first valid time found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Latest Time

Start from latest bus time and work backwards

Simulate Boarding

For each time, simulate all passengers boarding

Check Success

Return first valid arrival time found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* buses, int busesSize, int* passengers, int passengersSize, int capacity) {
    int maxTime = 0;
    for (int i = 0; i < busesSize; i++) {
        if (buses[i] > maxTime) maxTime = buses[i];
    }
    
    for (int arrivalTime = maxTime; arrivalTime >= 1; arrivalTime--) {
        int conflict = 0;
        for (int i = 0; i < passengersSize; i++) {
            if (passengers[i] == arrivalTime) {
                conflict = 1;
                break;
            }
        }
        if (conflict) continue;
        
        int* allPassengers = (int*)malloc((passengersSize + 1) * sizeof(int));
        for (int i = 0; i < passengersSize; i++) {
            allPassengers[i] = passengers[i];
        }
        allPassengers[passengersSize] = arrivalTime;
        qsort(allPassengers, passengersSize + 1, sizeof(int), compare);
        
        int* busesSorted = (int*)malloc(busesSize * sizeof(int));
        for (int i = 0; i < busesSize; i++) {
            busesSorted[i] = buses[i];
        }
        qsort(busesSorted, busesSize, sizeof(int), compare);
        
        int passengerIdx = 0;
        int caughtBus = 0;
        
        for (int i = 0; i < busesSize; i++) {
            int busTime = busesSorted[i];
            int boarded = 0;
            
            while (passengerIdx < passengersSize + 1 && boarded < capacity && allPassengers[passengerIdx] <= busTime) {
                if (allPassengers[passengerIdx] == arrivalTime) {
                    caughtBus = 1;
                }
                passengerIdx++;
                boarded++;
            }
            
            if (caughtBus) {
                free(allPassengers);
                free(busesSorted);
                return arrivalTime;
            }
        }
        
        free(allPassengers);
        free(busesSorted);
    }
    
    return 1;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int buses[1000], busesSize = 0;
    char *token = strtok(line + 1, ",]");
    while (token) {
        buses[busesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int passengers[1000], passengersSize = 0;
    token = strtok(line + 1, ",]");
    while (token) {
        passengers[passengersSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int capacity;
    scanf("%d", &capacity);
    
    printf("%d\n", solution(buses, busesSize, passengers, passengersSize, capacity));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(T×(N+M))

For each time T, simulate boarding process with N buses and M passengers

✓ Linear Growth

Space Complexity

O(M)

Copy passenger array for simulation

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

486 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try Every Time — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler