Door Crossing Times with Direction Priority
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
People are indexed from 0 through n - 1. Person i arrives at arrival[i] and wants to use one door in direction state[i]: 0 means enter and 1 means exit. The arrival array is sorted in nondecreasing order.
The door serves at most one person per second. Among people who have arrived and are still waiting:
- If the door was used in the previous second, that same direction has priority.
- If the door was unused in the previous second, exiting has priority.
- Within one direction, the smallest person index goes first.
Return an array answer where answer[i] is the second when person i uses the door. When both queues are empty, jump directly to the next arrival time; the immediately preceding second is then idle.
Function
timeTaken(arrival: int[], state: int[]) → int[]Examples
Example 1
arrival = [0,0,1,5]state = [0,1,1,0]return = [2,0,1,5]The door was idle before second 0, so person 1 exits first. Exiting retains priority for person 2 at second 1; person 0 enters at second 2, and person 3 enters after the idle gap.
Example 2
arrival = [0,1,1,3,3]state = [0,1,0,0,1]return = [0,2,1,4,3]Entering at second 0 gives entering priority at second 1. Person 1 then exits at second 2; exit priority therefore serves person 4 at second 3 before person 3 enters.
Example 3
arrival = [0,2,2]state = [0,0,1]return = [0,3,2]Second 1 is idle, so exit regains priority when persons 1 and 2 arrive together at second 2.
Constraints
1 <= arrival.length == state.length <= 100000.0 <= arrival[i] <= 1000000000, andarrivalis nondecreasing.state[i]is0or1.