Turnstile Times
MediumQueue · Amazon
n people want to pass through a single turnstile. Person i arrives at second arrival[i] and wants to go in direction direction[i]: 0 means entering and 1 means exiting. arrival is sorted in nondecreasing order.
Exactly one person can pass per second, and a person can pass any time at or after their arrival. At each second, if anyone is waiting:
- If people are waiting in only one direction, the earliest arrival (smallest index) in that direction passes.
- If people are waiting in both directions, the direction is chosen by what happened in the previous second:
- turnstile unused in the previous second: an exiting person goes first;
- used for exiting in the previous second: an exiting person goes first;
- used for entering in the previous second: an entering person goes first.
- Within a direction, people always pass in order of index.
Return a list answer where answer[i] is the second at which person i passes through.
Example 1
- Input:
- arrival = [0, 1, 1, 3, 3], direction = [1, 0, 1, 0, 1]
- Output:
- [0, 2, 1, 3, 4]
- Explanation
- At second 0 only person 0 (exit) is waiting. At second 1 person 1 (enter) and person 2 (exit) both wait, and the turnstile was just used to exit, so person 2 goes; person 1 follows at second 2. At second 3 persons 3 (enter) and 4 (exit) wait and the last use was entering, so person 3 goes first and person 4 passes at second 4.
Example 2
- Input:
- arrival = [2, 2, 2, 3], direction = [0, 0, 1, 1]
- Output:
- [4, 5, 2, 3]
- Explanation
- At second 2 the turnstile was idle the second before, so the exiting person 2 goes first. Person 3 arrives at second 3 and, because the last use was an exit, also goes ahead of the two people entering, who pass at seconds 4 and 5.
Example 3
- Input:
- arrival = [0, 0, 4], direction = [0, 1, 0]
- Output:
- [1, 0, 4]
- Explanation
- At second 0 both directions wait and the turnstile was idle, so person 1 exits first and person 0 enters at second 1. Person 2 arrives at second 4 to an empty turnstile and passes immediately.
Constraints
1 <= arrival.length == direction.length <= 10^50 <= arrival[i] <= 10^9, andarrivalis nondecreasingdirection[i]is0(enter) or1(exit)