Time taken to cross the door

Array Queue Simulation

50.1% acceptance

Mar 31, 2026

117

There are n persons numbered from 0 to n - 1 and a door. Each person can enter or exit through the door once, taking one second. You are given a non-decreasing integer array arrival of size n, where arrival[i] is the arrival time of the ith person at the door. You are also given an array state of size n, where state[i] is 0 if person i wants to enter through the door or 1 if they want to exit through the door. If two or more persons want to use the door at the same time, they follow the following rules: If the door was not used in the previous second, then the person who wants to exit goes first. If the door was used in the previous second for entering, the person who wants to enter goes first. If the door was used in the previous second for exiting, the person who wants to exit goes first. If multiple persons want to go in the same direction, the person with the smallest index goes first. Return an array answer of size n where answer[i] is the second at which the ith person crosses the door. Note that: Only one person can cross the door at each second. A person may arrive at the door and wait without entering or exiting to follow the mentioned rules.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn time_taken(arrival: Vec<i32>, state: Vec<i32>) -> Vec<i32> {
    use std::collections::VecDeque;
    let n = arrival.len();
    let mut answer = vec![0i32; n];
    let mut enter_q: VecDeque<usize> = VecDeque::new();
    let mut exit_q: VecDeque<usize> = VecDeque::new();
    let mut t = 0i32;
    let mut last_used = -1i32; // -1 = not used, 0 = enter, 1 = exit
    let mut i = 0;
    while i < n || !enter_q.is_empty() || !exit_q.is_empty() {
      // Add all persons arriving at time t
      while i < n && arrival[i] <= t {
        if state[i] == 0 {
          enter_q.push_back(i);
        } else {
          exit_q.push_back(i);
        }
        i += 1;
      }
      if enter_q.is_empty() && exit_q.is_empty() {
        // Fast forward to next arrival
        t = arrival[i];
        last_used = -1;
        continue;
      }
      // Determine priority
      let exit_priority = last_used == -1 || last_used == 1;
      if exit_priority {
        if !exit_q.is_empty() {
          let p = exit_q.pop_front().unwrap();
          answer[p] = t;
          last_used = 1;
        } else {
          let p = enter_q.pop_front().unwrap();
          answer[p] = t;
          last_used = 0;
        }
      } else {
        if !enter_q.is_empty() {
          let p = enter_q.pop_front().unwrap();
          answer[p] = t;
          last_used = 0;
        } else {
          let p = exit_q.pop_front().unwrap();
          answer[p] = t;
          last_used = 1;
        }
      }
      t += 1;
    }
    answer
  }
}