Compute Turnstile Crossing Times
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given `n` people waiting to use a single-door turnstile. Each person has:
- `time[i]`: the time when person `i` arrives at the turnstile.
- `direction[i]`: the direction person `i` wants to go, where `0` means enter and `1` means exit.
The arrays are ordered by nondecreasing arrival time, and each index `i` represents a distinct person. At most one person can use the turnstile at each integer time unit.
When multiple people are waiting at the same time, the turnstile chooses who goes next using these rules:
1. If the turnstile was used in the previous time unit, then people going in the same direction as the previous user have priority.
2. If the turnstile was not used in the previous time unit, then exiting people have priority.
3. If multiple people with the same priority are waiting, the person with the smaller index goes first.
Return an array `answer` of length `n`, where `answer[i]` is the time when person `i` uses the turnstile.
Your solution should run in `O(n)` time by jumping the current time forward when no one is waiting, instead of simulating every time unit between the minimum and maximum arrival times.
Quick Answer: This question evaluates proficiency in queue simulation, event-driven scheduling, and handling priority and tie-breaking rules while achieving linear time complexity.
You are given n people waiting to use a single-door turnstile. Person i arrives at time[i] and wants to use the turnstile in direction[i], where 0 means enter and 1 means exit. The arrays are ordered by nondecreasing arrival time, and each index represents a distinct person.
At each integer time unit, at most one person can use the turnstile. A person is considered waiting if they have arrived and have not used the turnstile yet.
When multiple people are waiting at the same time, choose who goes next using these rules:
1. If the turnstile was used in the previous time unit, then people going in the same direction as the previous user have priority.
2. If the turnstile was not used in the previous time unit, then exiting people have priority.
3. If multiple waiting people have the same priority, the person with the smaller index goes first.
Return an array answer of length n, where answer[i] is the time when person i uses the turnstile.
Your solution should run in O(n) time by jumping the current time forward whenever nobody is waiting, instead of simulating every time unit across idle gaps.
Constraints
- 0 <= n == len(time) == len(direction) <= 2 * 10^5
- 0 <= time[i] <= 10^9
- direction[i] is either 0 or 1
- time is sorted in nondecreasing order