The latest time to catch a bus

Array Two Pointers Binary Search Sorting

30.0% acceptance

Feb 25, 2026

530

799

You are given buses (departure times), passengers (arrival times), and capacity. Return the latest time you may arrive at the bus station to catch a bus (cannot arrive same time as another passenger).

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn latest_time_catch_the_bus(mut buses: Vec<i32>, mut passengers: Vec<i32>, capacity: i32) -> i32 {
    buses.sort_unstable();
    passengers.sort_unstable();
    let pass_set: std::collections::HashSet<i32> = passengers.iter().cloned().collect();

    let m = passengers.len();
    let mut j = 0usize;
    let mut last_full = false;
    let mut last_passenger = 0i32;

    for &bus in &buses {
      let mut cnt = 0;
      while j < m && passengers[j] <= bus && cnt < capacity {
        last_passenger = passengers[j];
        j += 1;
        cnt += 1;
      }
      last_full = cnt == capacity;
    }

    let upper = if !last_full { *buses.last().unwrap() } else { last_passenger - 1 };
    let mut t = upper;
    while t > 0 && pass_set.contains(&t) {
      t -= 1;
    }
    t
  }
}