Consider the following diagram. Once every 2 seconds a car enters from the top and travels down towards the exit. Once every 3 seconds a car enters from the left and travels to the right exit. In the beginning there are no cars. On the 2nd second a car will enter at the top. On the 3rd second another car will enter from the left. On the 6th second, cars will enter at both locations and so on. Once a car is on the road it will attempt to move towards its exit location, moving one square per second. If the traffic light is red for the given road then the car will not move and only move when the light is green. If the road is full of cars and a new car cannot enter the road, then an accident happens and everything comes to a stop. Cars that exit are taken off the road. There cannot be more than one car per square.

enter image description here

The traffic lights are broken, so you have been tasked to control them manually. Once per second you can switch the traffic light. If the light is red for the vertical road then it will become green for the horizontal road and vice versa. What is the most number of cars that can reach the exit in 100 seconds?

  • $\begingroup$ Can a car enter a given square the second another car leaves the same square? $\endgroup$
    – loopy walt
    Commented Apr 1, 2021 at 6:59
  • $\begingroup$ Also, do I understand correctly that cars will not move up to a red light but stop "in the middle of the road"? $\endgroup$
    – loopy walt
    Commented Apr 1, 2021 at 7:02
  • $\begingroup$ yes one car enters as the other one moves $\endgroup$ Commented Apr 1, 2021 at 7:08
  • $\begingroup$ yes they will move just before the intersection and stop there, like in real life $\endgroup$ Commented Apr 1, 2021 at 7:08

2 Answers 2


I say


which is

48 from entry1. Last car @t=96 barely makes it

31 from entry2. The car @t=96 barely does not make it, so the last one is the one @93


The intersection can support 1 car/second, while the flow is 5cars/6 seconds, so any easy algorithm will work.

For example:

Give priority to entry1 cars, so show red to entry2 cars if there is an entry1 car that wants to pass

For any algorithm,

The concurrent car spawning of t=96, which can exit at t=100, means only one of them will exit in time.


As an addition to the existing answer, I would say that

the system will operate continuously without accidents if the traffic lights were switched every second. This allows the vertical-road cars to run uninterruptibly (showing green when a car is in a square directly in front of the intersection), and the horizontal-road cars will wait at most 1 second per car. Since there are 2 free squares between the horizontal-road cars (if we extend the road to the left), there will always be enough space to not create a jam.

However, in the real-life situation with the same traffic flow it would be better

to leave the things as they are, more precisely, disable the traffic lights at all and give the vertical road the right of way (since there are more cars on that road). This will actually work in the very same manner.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.