Time to cross a bridge

Array Heap (Priority Queue) Simulation

44.4% acceptance

Feb 25, 2026

123

225

There are k workers who want to move n boxes from the right (old) warehouse to the left (new) warehouse. You are given the two integers n and k, and a 2D integer array time of size k x 4 where time[i] = [righti, picki, lefti, puti]. The warehouses are separated by a river and connected by a bridge. Initially, all k workers are waiting on the left side of the bridge. Cross the bridge to the right side in righti minutes. Pick a box from the right warehouse in picki minutes. Cross the bridge to the left side in lefti minutes. Put the box into the left warehouse in puti minutes. The ith worker is less efficient than the jth worker if either condition is met: lefti + righti > leftj + rightj lefti + righti == leftj + rightj and i > j Bridge rules: only one worker at a time. Prioritize least efficient worker on right side waiting to cross left. If none, send least efficient on left side to cross right. Return the elapsed minutes at which the last box reaches the left side of the bridge.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_crossing_time(n: i32, k: i32, time: Vec<Vec<i32>>) -> i32 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    let n = n as usize;
    let k = k as usize;

    // (efficiency, worker_index) - max-heap (least efficient = highest priority)
    let mut left_wait: BinaryHeap<(i32, i32)> = BinaryHeap::new();
    let mut right_wait: BinaryHeap<(i32, i32)> = BinaryHeap::new();
    // (finish_time, worker_index) - min-heap
    let mut left_work: BinaryHeap<Reverse<(i32, usize)>> = BinaryHeap::new();
    let mut right_work: BinaryHeap<Reverse<(i32, usize)>> = BinaryHeap::new();

    for i in 0..k {
      let eff = time[i][0] + time[i][2];
      left_wait.push((eff, i as i32));
    }

    let mut t = 0i32;
    let mut boxes_sent = 0usize;
    let mut ans = 0i32;

    while boxes_sent < n || !right_wait.is_empty() || !right_work.is_empty() {
      // Release workers who finished their task
      while let Some(&Reverse((done, idx))) = right_work.peek() {
        if done <= t {
          right_work.pop();
          let eff = time[idx][0] + time[idx][2];
          right_wait.push((eff, idx as i32));
        } else {
          break;
        }
      }
      while let Some(&Reverse((done, idx))) = left_work.peek() {
        if done <= t {
          left_work.pop();
          let eff = time[idx][0] + time[idx][2];
          left_wait.push((eff, idx as i32));
        } else {
          break;
        }
      }

      let can_send_left = !left_wait.is_empty() && boxes_sent < n;
      if right_wait.is_empty() && !can_send_left {
        // No one ready to cross, advance time
        let mut nxt = i32::MAX;
        if let Some(&Reverse((d, _))) = right_work.peek() {
          nxt = nxt.min(d);
        }
        if let Some(&Reverse((d, _))) = left_work.peek() {
          nxt = nxt.min(d);
        }
        if nxt < i32::MAX {
          t = nxt;
        }
        continue;
      }

      if !right_wait.is_empty() {
        // Least efficient on right crosses to left
        let (_, idx) = right_wait.pop().unwrap();
        let i = idx as usize;
        t += time[i][2];
        ans = ans.max(t);
        left_work.push(Reverse((t + time[i][3], i)));
      } else {
        // Least efficient on left crosses to right
        let (_, idx) = left_wait.pop().unwrap();
        let i = idx as usize;
        t += time[i][0];
        right_work.push(Reverse((t + time[i][1], i)));
        boxes_sent += 1;
      }
    }

    ans
  }
}