Intersection Manager

At each direction {N, E, S, W}, every 5s, there will be 0 or 1 car approaching the intersection. Each car has a destination direction {N, E, S, W}, and it will not be the same as the source direction. (No U turn!)

Assumptions: Arrival times given in advance One lane for each way The length of a round is 5s Right-hand drive

Assume that the length of a round is 5s.

Within 1 second, the manager will schedule some cars to go through the intersection without "conflict paths" and inform those cars. It will schedule at most 1 car at each direction.

Those cars which get scheduled go through the intersection within 4 seconds. Those cars which do not get scheduled will wait the next round. However, a car may move forward if one of its front cars gets scheduled.

Objective: Minimize the average waiting time of each car No conflicts are allowed

Note: if there is a car not scheduled at one direction, we can guarantee that there is a car at that direction (right before the stop line) in the next round.

Input: Each direction has a binary sequence: 0, 1, 1, ... Each 1 is associated with a source-destination direction: 1 (S-N) Conflict vs. no conflict Assume one lane for each way S: straight R: right turn L: left turn Check conflict table (consider symmetry/rotation) test:

Input test.: N: 1S 1E 00 E: 1W 00 00 S: 00 00 00 W: 00 00 00 Output test. 1S 1E 00 00 00 1W 00 00 00 00 00 00 Give Output of these 3 inputs 1. N: 00 1E 00 00 1S 1E 00 00 E: 00 1S 1S 1N 00 00 1W 00 S: 1N 1E 1W 1W 1N 1E 1W 00 W: 1N 1E 1S 00 00 1N 00 1E 2. N: 1E 00 1E 00 1S 1E 00 00 E: 00 1S 1S 1S 1N 00 1W 00 S: 1E 1E 1E 1E 00 1E 1W 00 W: 1E 1E 00 00 1E 1N 00 1E 3. N: 00 1E 00 00 1E 00 00 00 E: 00 00 00 1S 00 1N 1S 00 S: 1E 1W 1W 1W 1N 00 1N 1E W: 1N 00 1N 00 00 1N 00 1E Can be calculated or use c++ code: