Lily's Blog

Mobile Application Development and Competitive Practice Problems

Algorithms: Traffic Control

There are N cars entering a one way road having two lanes. There is a divider between lanes so once a car enters a lane, it can't change. Also lanes are narrow so overtaking is not possible and hence a car might have to slow down to avoid bumping in the car in front of it. Each car has a maximum speed which is given to you. A car driver is happy if his car doesn't need to slow down and can drive at its maximum speed.

You're the traffic policeman and it is your job to assign certain cars to lane 1 and remaining to lane 2. Within a lane order of cars is same as their initial order. How should you assign lanes to each car so that maximum drivers are happy?

Problem written by Pradeep George Mathias , Rudradev Basak and Nikhil Garg, used in 2nd team selection test at IOI training camp for Indian team, 2012.