Skip to content

2534. Time Taken to Cross the Door 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  vector<int> timeTaken(vector<int>& arrival, vector<int>& state) {
    const int n = arrival.size();
    vector<int> ans(n);
    vector<queue<int>> qs(2);  // qs[0] := enter queue, qs[1] := exit queue
    int time = 0;
    int d = 1;  // 0 := enter, 1 := exit

    for (int i = 0; i < n; ++i) {
      popQueues(time, d, arrival[i], qs, ans);
      // If the door was not used in the previous second, then the person who
      // wants to exit goes first.
      if (arrival[i] > time) {
        time = arrival[i];  // Forward `time` to now.
        d = 1;
      }
      qs[state[i]].push(i);
    }

    popQueues(time, d, 200'000, qs, ans);
    return ans;
  }

 private:
  void popQueues(int& time, int& d, int arrivalTime, vector<queue<int>>& qs,
                 vector<int>& ans) {
    while (arrivalTime > time && (!qs[0].empty() || !qs[1].empty())) {
      if (qs[d].empty())
        d ^= 1;
      ans[qs[d].front()] = time++, qs[d].pop();
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  public int[] timeTaken(int[] arrival, int[] state) {
    final int n = arrival.length;
    int[] ans = new int[n];
    Queue<Integer>[] qs = new Queue[2];
    qs[0] = new LinkedList<>(); // enter queue
    qs[1] = new LinkedList<>(); // exit queue

    for (int i = 0; i < n; ++i) {
      popQueues(arrival[i], qs, ans);
      // If the door was not used in the previous second, then the person who
      // wants to exit goes first.
      if (arrival[i] > time) {
        time = arrival[i]; // Forward `time` to now.
        d = 1;             // Reset priority to exit.
      }
      qs[state[i]].offer(i);
    }

    popQueues(200000, qs, ans);
    return ans;
  }

  private int time = 0;
  private int d = 1; // 0: enter, 1: exit

  private void popQueues(int arrivalTime, Queue<Integer>[] qs, int[] ans) {
    while (arrivalTime > time && (!qs[0].isEmpty() || !qs[1].isEmpty())) {
      if (qs[d].isEmpty())
        d ^= 1; // Toggle between enter (0) and exit (1)
      ans[qs[d].poll()] = time++;
    }
  }
}