Busy Intersection
Citadel● MediumFULLTIMEOAProblem statement
At a busy intersection, people wait in one of two queues, identified by direction 0 or 1. Person i arrives at integer second arrivalTimes[i] and joins queue directions[i].
Exactly one waiting person can pass through the intersection during each second. At the start of a second, choose the next person using these rules:
- If only one queue is nonempty, serve the person at the front of that queue.
- If both queues are nonempty and someone passed during the immediately previous second, give priority to the same direction used in that previous second.
- If both queues are nonempty and the immediately previous second was idle, give priority to direction
1.
Each queue is first-in, first-out. People in the same direction with the same arrival time are ordered by their original indices.
Return an array result where result[i] is the second when person i passes through the intersection.
Function
serviceTimes(arrivalTimes: int[], directions: int[]) → int[]Examples
Example 1
arrivalTimes = [0,0,1,5]directions = [0,1,1,0]return = [2,0,1,5]At second 0, both queues are waiting after an idle period, so person 1 from direction 1 passes. Direction 1 keeps priority at second 1, so person 2 passes. Person 0 then passes at second 2, and person 3 passes upon arriving at second 5.
Example 2
arrivalTimes = [0,1,1,3,3]directions = [0,1,0,0,1]return = [0,2,1,4,3]Person 0 establishes direction 0 at second 0, so person 2 wins the two-queue choice at second 1. Person 1 follows at second 2. At second 3, direction 1 retains priority for person 4, followed by person 3.
Example 3
arrivalTimes = [2,2,4]directions = [0,1,0]return = [3,2,4]The intersection is idle before second 2, so direction 1 wins the simultaneous arrival. Person 0 passes at second 3, and person 2 passes at second 4.
Constraints
1 ≤ arrivalTimes.length ≤ 10^5.directions.length = arrivalTimes.length.0 ≤ arrivalTimes[i] ≤ 10^9.arrivalTimesis sorted in nondecreasing order.directions[i]is either0or1.