FastPrep
Problem · Array

Busy Intersection

Learn this problem
● MediumIMC logoIMCFULLTIMEOA

Problem statement

Two one-way streets meet at a single-lane intersection. Cars arriving from Main Street have direction 0, and cars arriving from 1st Avenue have direction 1. Each street has its own first-in, first-out queue, and exactly one waiting car can cross during each second.

For car i, arrival[i] is the second when it reaches the intersection and direction[i] is its street. Cars are indexed in input order. When multiple cars from the same street arrive at the same second, the lower-indexed car is earlier in that street's queue.

At each second, use these rules:

  • If only one street has waiting cars, the first car from that street crosses.
  • If both streets have waiting cars and no car crossed during the previous second, the first car from direction 1 crosses.
  • If both streets have waiting cars and a car crossed during the previous second, the first car from the same direction as that previous car crosses.

Return an integer array result where result[i] is the second when car i crosses the intersection.

Function

getResult(arrival: int[], direction: int[]) → int[]

Examples

Example 1

arrival = [0,0,1,4]direction = [0,1,1,0]return = [2,0,1,4]

At second 0, both streets have a waiting car and the previous second was idle, so car 1 from direction 1 crosses. Car 2 arrives at second 1 and direction 1 keeps priority, so it crosses next. Car 0 then crosses at second 2. No car is waiting at second 3, and car 3 crosses when it arrives at second 4.

Example 2

arrival = [0,1,1,3,3]direction = [0,1,0,0,1]return = [0,2,1,4,3]

Car 0 is alone at second 0 and crosses. At second 1, cars 1 and 2 are both waiting, so direction 0 retains priority and car 2 crosses. Car 1 crosses at second 2. Cars 3 and 4 arrive at second 3; because direction 1 crossed in the previous second, car 4 crosses before car 3.

Constraints

  • 1 <= arrival.length <= 10^5
  • direction.length == arrival.length
  • 0 <= arrival[i] <= 10^9
  • arrival is sorted in nondecreasing order.
  • direction[i] is either 0 or 1.

More IMC problems

drafts saved locally
class Solution {
    public int[] getResult(int[] arrival, int[] direction) {
        // Write your code here.
        return new int[0];
    }
}
arrival[0,0,1,4]
direction[0,1,1,0]
expected[2,0,1,4]
checking account