| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
Hard |
|
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.length1 <= n <= 1050 <= arrival[i] <= narrivalis sorted in non-decreasing order.state[i]is either0or1.
We define two queues, where
We maintain a variable
We traverse the array
Then we check if both queues
Next, we increment the time
The time complexity is
class Solution:
def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
q = [deque(), deque()]
n = len(arrival)
t = i = 0
st = 1
ans = [0] * n
while i < n or q[0] or q[1]:
while i < n and arrival[i] <= t:
q[state[i]].append(i)
i += 1
if q[0] and q[1]:
ans[q[st].popleft()] = t
elif q[0] or q[1]:
st = 0 if q[0] else 1
ans[q[st].popleft()] = t
else:
st = 1
t += 1
return ansclass Solution {
public int[] timeTaken(int[] arrival, int[] state) {
Deque<Integer>[] q = new Deque[2];
Arrays.setAll(q, i -> new ArrayDeque<>());
int n = arrival.length;
int t = 0, i = 0, st = 1;
int[] ans = new int[n];
while (i < n || !q[0].isEmpty() || !q[1].isEmpty()) {
while (i < n && arrival[i] <= t) {
q[state[i]].add(i++);
}
if (!q[0].isEmpty() && !q[1].isEmpty()) {
ans[q[st].poll()] = t;
} else if (!q[0].isEmpty() || !q[1].isEmpty()) {
st = q[0].isEmpty() ? 1 : 0;
ans[q[st].poll()] = t;
} else {
st = 1;
}
++t;
}
return ans;
}
}class Solution {
public:
vector<int> timeTaken(vector<int>& arrival, vector<int>& state) {
int n = arrival.size();
queue<int> q[2];
int t = 0, i = 0, st = 1;
vector<int> ans(n);
while (i < n || !q[0].empty() || !q[1].empty()) {
while (i < n && arrival[i] <= t) {
q[state[i]].push(i++);
}
if (!q[0].empty() && !q[1].empty()) {
ans[q[st].front()] = t;
q[st].pop();
} else if (!q[0].empty() || !q[1].empty()) {
st = q[0].empty() ? 1 : 0;
ans[q[st].front()] = t;
q[st].pop();
} else {
st = 1;
}
++t;
}
return ans;
}
};func timeTaken(arrival []int, state []int) []int {
n := len(arrival)
q := [2][]int{}
t, i, st := 0, 0, 1
ans := make([]int, n)
for i < n || len(q[0]) > 0 || len(q[1]) > 0 {
for i < n && arrival[i] <= t {
q[state[i]] = append(q[state[i]], i)
i++
}
if len(q[0]) > 0 && len(q[1]) > 0 {
ans[q[st][0]] = t
q[st] = q[st][1:]
} else if len(q[0]) > 0 || len(q[1]) > 0 {
if len(q[0]) == 0 {
st = 1
} else {
st = 0
}
ans[q[st][0]] = t
q[st] = q[st][1:]
} else {
st = 1
}
t++
}
return ans
}function timeTaken(arrival: number[], state: number[]): number[] {
const n = arrival.length;
const q: number[][] = [[], []];
let [t, i, st] = [0, 0, 1];
const ans: number[] = Array(n).fill(0);
while (i < n || q[0].length || q[1].length) {
while (i < n && arrival[i] <= t) {
q[state[i]].push(i++);
}
if (q[0].length && q[1].length) {
ans[q[st][0]] = t;
q[st].shift();
} else if (q[0].length || q[1].length) {
st = q[0].length ? 0 : 1;
ans[q[st][0]] = t;
q[st].shift();
} else {
st = 1;
}
t++;
}
return ans;
}use std::collections::VecDeque;
impl Solution {
pub fn time_taken(arrival: Vec<i32>, state: Vec<i32>) -> Vec<i32> {
let n = arrival.len();
let mut q = vec![VecDeque::new(), VecDeque::new()];
let mut t = 0;
let mut i = 0;
let mut st = 1;
let mut ans = vec![-1; n];
while i < n || !q[0].is_empty() || !q[1].is_empty() {
while i < n && arrival[i] <= t {
q[state[i] as usize].push_back(i);
i += 1;
}
if !q[0].is_empty() && !q[1].is_empty() {
ans[*q[st].front().unwrap()] = t;
q[st].pop_front();
} else if !q[0].is_empty() || !q[1].is_empty() {
st = if q[0].is_empty() { 1 } else { 0 };
ans[*q[st].front().unwrap()] = t;
q[st].pop_front();
} else {
st = 1;
}
t += 1;
}
ans
}
}