2534. Time Taken to Cross the Door π
Description
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.
Example 1:
Input: arrival = [0,1,1,2,4], state = [0,1,0,0,1] Output: [0,3,1,2,4] Explanation: At each second we have the following: - At t = 0: Person 0 is the only one who wants to enter, so they just enter through the door. - At t = 1: Person 1 wants to exit, and person 2 wants to enter. Since the door was used the previous second for entering, person 2 enters. - At t = 2: Person 1 still wants to exit, and person 3 wants to enter. Since the door was used the previous second for entering, person 3 enters. - At t = 3: Person 1 is the only one who wants to exit, so they just exit through the door. - At t = 4: Person 4 is the only one who wants to exit, so they just exit through the door.
Example 2:
Input: arrival = [0,0,0], state = [1,0,1] Output: [0,2,1] Explanation: At each second we have the following: - At t = 0: Person 1 wants to enter while persons 0 and 2 want to exit. Since the door was not used in the previous second, the persons who want to exit get to go first. Since person 0 has a smaller index, they exit first. - At t = 1: Person 1 wants to enter, and person 2 wants to exit. Since the door was used in the previous second for exiting, person 2 exits. - At t = 2: Person 1 is the only one who wants to enter, so they just enter through the door.
Constraints:
n == arrival.length == state.length
1 <= n <= 105
0 <= arrival[i] <= n
arrival
is sorted in non-decreasing order.state[i]
is either0
or1
.
Solutions
Solution 1: Queue + Simulation
We define two queues, where $q[0]$ stores the indices of people who want to enter, and $q[1]$ stores the indices of people who want to exit.
We maintain a variable $t$ to represent the current time, and a variable $st$ to represent the current state of the door. When $st = 1$, it means the door is not in use or someone exited in the previous second. When $st = 0$, it means someone entered in the previous second. Initially, $t = 0$ and $st = 1$.
We traverse the array $\textit{arrival}$. For each person, if the current time $t$ is less than or equal to the time the person arrives at the door $\textit{arrival}[i]$, we add the person's index to the corresponding queue $q[\text{state}[i]]$.
Then we check if both queues $q[0]$ and $q[1]$ are not empty. If both are not empty, we dequeue the front element from the queue $q[st]$ and assign the current time $t$ to the person's passing time. If only one queue is not empty, we update the value of $st$ based on which queue is not empty, then dequeue the front element from that queue and assign the current time $t$ to the person's passing time. If both queues are empty, we update the value of $st$ to $1$, indicating the door is not in use.
Next, we increment the time $t$ by $1$ and continue traversing the array $\textit{arrival}$ until all people have passed through the door.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ represents the length of the array $\textit{arrival}$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
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 |
|