Traffic Light Controlled Intersection

Easy

Asked by:

9 views

Topics:

Dynamic Programming

There is an intersection of two roads. First road is running from north to south in a straight line (i.e. north-south road). Second road is running from west to east in a straight line (i.e. west-east road).

These two roads intersect at a single point where traffic is controlled by a traffic light system.

There are two different threads modeling cars in each road. Each thread tries to increase the number of cars passing through the intersection.

Write a simulation of a traffic light controlled intersection using three functions:

carArrived(carId, roadId, direction, acquireGreen, releaseGreen):
- A car arrives at the intersection identified by its integer carId.
- The road the car is traveling on is identified by its integer roadId.
- The direction a car is traveling is indicated by an enum direction with possible values:
  - NORTH
  - SOUTH
  - WEST
  - EAST
- acquireGreen is a function you should call to acquire access to the intersection.
- releaseGreen is a function you should call to release access to the intersection.

isGreen(): Returns true if the current traffic light is green on car's roadId, otherwise returns false.

turnGreen(): Turns the traffic light to green on the roadId.

Example 1:

Input: cars = [1,3,5,2,4], directions = ["NORTH","WEST","SOUTH","EAST","NORTH"],
roads = [1,2,1,2,1]
Output: ["NORTH","WEST","SOUTH","EAST","NORTH"]

Explanation:

The simulation follows these steps:

Car 1 arrives at the intersection traveling NORTH on road 1. Since the light is initially green on road 1, the car passes immediately through the intersection.
Car 3 arrives at the intersection traveling SOUTH on road 1. Since the light is still green on road 1, the car passes immediately through the intersection.
Car 5 arrives at the intersection traveling NORTH on road 1. Since the light is still green on road 1, the car passes immediately through the intersection.
Car 2 arrives at the intersection traveling WEST on road 2. Since the light is green on road 1, the car waits.
Car 4 arrives at the intersection traveling EAST on road 2. Since the light is green on road 1, the car waits.
The traffic light turns green on road 2.
Car 2 passes through the intersection traveling WEST on road 2.
Car 4 passes through the intersection traveling EAST on road 2.

Example 2:

Input: cars = [1,2,3,4,5], directions = ["NORTH","EAST","WEST","SOUTH","NORTH"], roads = [1,2,2,1,1]
Output: ["NORTH","EAST","WEST","SOUTH","NORTH"]

Constraints:

1 <= cars.length <= 20
cars.length = directions.length
cars.length = roads.length
1 <= carId <= 20
roadId is one of the two possible values: {1,2}
direction is one of the four possible values: {"NORTH","SOUTH","EAST","WEST"}
All cars are arriving at the intersection at different times.

Try coding it in LeetCode

Traffic Light Controlled Intersection

Easy

Asked by:

9 views

Topics:

Dynamic Programming

There is an intersection of two roads. First road is running from north to south in a straight line (i.e. north-south road). Second road is running from west to east in a straight line (i.e. west-east road).

These two roads intersect at a single point where traffic is controlled by a traffic light system.

There are two different threads modeling cars in each road. Each thread tries to increase the number of cars passing through the intersection.

Write a simulation of a traffic light controlled intersection using three functions:

carArrived(carId, roadId, direction, acquireGreen, releaseGreen):
- A car arrives at the intersection identified by its integer carId.
- The road the car is traveling on is identified by its integer roadId.
- The direction a car is traveling is indicated by an enum direction with possible values:
  - NORTH
  - SOUTH
  - WEST
  - EAST
- acquireGreen is a function you should call to acquire access to the intersection.
- releaseGreen is a function you should call to release access to the intersection.

isGreen(): Returns true if the current traffic light is green on car's roadId, otherwise returns false.

turnGreen(): Turns the traffic light to green on the roadId.

Example 1:

Input: cars = [1,3,5,2,4], directions = ["NORTH","WEST","SOUTH","EAST","NORTH"],
roads = [1,2,1,2,1]
Output: ["NORTH","WEST","SOUTH","EAST","NORTH"]

Explanation:

The simulation follows these steps:

Car 1 arrives at the intersection traveling NORTH on road 1. Since the light is initially green on road 1, the car passes immediately through the intersection.
Car 3 arrives at the intersection traveling SOUTH on road 1. Since the light is still green on road 1, the car passes immediately through the intersection.
Car 5 arrives at the intersection traveling NORTH on road 1. Since the light is still green on road 1, the car passes immediately through the intersection.
Car 2 arrives at the intersection traveling WEST on road 2. Since the light is green on road 1, the car waits.
Car 4 arrives at the intersection traveling EAST on road 2. Since the light is green on road 1, the car waits.
The traffic light turns green on road 2.
Car 2 passes through the intersection traveling WEST on road 2.
Car 4 passes through the intersection traveling EAST on road 2.

Example 2:

Input: cars = [1,2,3,4,5], directions = ["NORTH","EAST","WEST","SOUTH","NORTH"], roads = [1,2,2,1,1]
Output: ["NORTH","EAST","WEST","SOUTH","NORTH"]

Constraints:

1 <= cars.length <= 20
cars.length = directions.length
cars.length = roads.length
1 <= carId <= 20
roadId is one of the two possible values: {1,2}
direction is one of the four possible values: {"NORTH","SOUTH","EAST","WEST"}
All cars are arriving at the intersection at different times.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

How is the intersection represented? Is it simply a set of roads, or do I need to consider the physical layout and connections between roads?
How are the traffic lights represented? What states can they be in (e.g., red, yellow, green), and how long do they remain in each state?
What is the goal of the traffic light control system? Is it to minimize waiting time, maximize throughput, or some other objective?
How is traffic flow represented? Do I need to simulate individual cars, or can I work with aggregate traffic volumes?
What are the specific requirements for the output? Do I need to provide a schedule for the traffic lights, a simulation of traffic flow, or something else?

Brute Force Solution

Approach

The brute force approach to managing traffic lights at an intersection involves checking every possible combination of light timings. We'll explore all scenarios, from very short green light durations to very long ones, to see which timing configuration minimizes waiting vehicles. This means literally trying every possible green light duration combination for the different directions and seeing which one works best.

Here's how the algorithm would work step-by-step:

Start with the simplest idea: give one road a very short green light duration.
See how many cars pass through that intersection during that short green duration and how many other cars are waiting on the other roads.
Repeat this, gradually increasing the green light duration for that road, recording how the waiting cars change on other roads.
Next, instead of changing only the first road, hold it constant and experiment with the second road's green light duration, again tracking the waiting cars on other roads.
Do this for every possible combination of green light durations for each road approaching the intersection.
Keep track of the total number of waiting cars for each tested light duration scenario.
Finally, from all the scenarios, choose the combination of green light durations that results in the fewest total number of waiting cars across all the roads.

Code Implementation

def traffic_light_brute_force(roads, max_green_time):    best_timing = None
    min_waiting_cars = float('inf')

    # Iterate through all possible green light durations for each road
    for green_time_road_one in range(1, max_green_time + 1):
        for green_time_road_two in range(1, max_green_time + 1):
            for green_time_road_three in range(1, max_green_time + 1):
                for green_time_road_four in range(1, max_green_time + 1):
                    green_light_durations = [
                        green_time_road_one,
                        green_time_road_two,
                        green_time_road_three,
                        green_time_road_four,
                    ]

                    total_waiting_cars = 0
                    # Simulate traffic flow for the current light durations

                    for road_index, road in enumerate(roads):
                        waiting_cars = road['arrival_rate'] * (sum(green_light_durations) - green_light_durations[road_index])
                        total_waiting_cars += waiting_cars

                    # Check if this combination results in fewer waiting cars
                    if total_waiting_cars < min_waiting_cars:
                        min_waiting_cars = total_waiting_cars
                        best_timing = green_light_durations

    # Return the best timing found
    return best_timing

Big(O) Analysis

Time Complexity

O(d^r) – The algorithm explores all possible combinations of green light durations for each road. Let 'd' represent the number of possible discrete green light durations that we are testing for each road (e.g., 1 second, 2 seconds, up to some maximum). Let 'r' be the number of roads approaching the intersection. Since we are iterating through every possible duration for every road, the total number of combinations tested is d * d * ... * d (r times), which is d^r. Therefore, the time complexity is O(d^r), representing the exhaustive search across all duration combinations for each road.

Space Complexity

O(1) – The algorithm, as described, primarily involves iterating through different green light durations and tracking the 'total number of waiting cars for each tested light duration scenario'. The explanation mentions keeping track of the total waiting cars. This implies storing a running minimum of waiting cars and the corresponding green light durations that achieved it. These variables (minimum waiting cars, optimal durations) are independent of the input size N (where N likely represents the range of green light durations or a combination of road counts and duration ranges). Therefore, the auxiliary space used is constant.

Optimal Solution

Approach

The key to efficiently managing traffic flow at an intersection is to grant access to roads in a way that minimizes overall waiting time. The system should change lights based on the perceived need, prioritizing fairness and preventing starvation for any single direction.

Here's how the algorithm would work step-by-step:

First, figure out a good way to represent the intersection and the different directions traffic can flow.
Determine how to keep track of waiting vehicles for each direction.
Create a system that checks regularly to see which direction has been waiting the longest or has the most waiting vehicles.
Give the right-of-way (green light) to the direction that needs it most, but ensure no single direction is favored too heavily to avoid starving other directions.
Implement a reasonable time limit for each green light to prevent any one direction from holding up others indefinitely.
Include a short yellow light phase after the green light to give drivers enough time to react to the changing signals.
After one direction has had its turn, switch to the next most deserving direction based on the same waiting criteria. Repeat the process to continuously manage the intersection.
Consider adding a check for emergency vehicles and immediately give them the right-of-way if they are detected to ensure safety.

Code Implementation

class TrafficLightControlledIntersection:
    def __init__(self, directions):
        self.directions = directions
        self.waiting_vehicles = {direction: 0 for direction in directions}
        self.current_green_direction = None
        self.green_light_duration = 10
        self.yellow_light_duration = 3
        self.time = 0

    def update_waiting_vehicles(self, direction, number_of_vehicles):
        self.waiting_vehicles[direction] += number_of_vehicles

    def choose_next_direction(self):
        # Prioritize directions with the most waiting vehicles
        best_direction = None
        max_waiting_vehicles = -1
        for direction, vehicles in self.waiting_vehicles.items():
            if vehicles > max_waiting_vehicles and direction != self.current_green_direction:
                max_waiting_vehicles = vehicles
                best_direction = direction

        if best_direction is None:
            #If all directions have 0 vehicles, cycle to the next one.
            directions_list = list(self.directions)
            if self.current_green_direction is None:
                return directions_list[0]
            current_index = directions_list.index(self.current_green_direction)
            next_index = (current_index + 1) % len(directions_list)
            return directions_list[next_index]

        return best_direction

    def handle_emergency_vehicle(self, emergency_direction):
        #Immediately give right-of-way to emergency vehicles
        self.set_light(emergency_direction)

    def set_light(self, direction):
        print(f"Time: {self.time} - Setting light to GREEN for {direction}")
        self.current_green_direction = direction
        self.waiting_vehicles[direction] = 0
        self.time += self.green_light_duration
        print(f"Time: {self.time} - Setting light to YELLOW for {direction}")
        self.time += self.yellow_light_duration
        print(f"Time: {self.time} - Setting light to RED for {direction}")

    def run_simulation(self, duration):
        while self.time < duration:
            next_direction = self.choose_next_direction()

            # Only change the light if there is a valid next direction.
            if next_direction:
                self.set_light(next_direction)
            else:
                self.time += 1

if __name__ == '__main__':
    intersection = TrafficLightControlledIntersection(['North', 'South', 'East', 'West'])

    # Simulate vehicle arrivals
    intersection.update_waiting_vehicles('North', 5)
    intersection.update_waiting_vehicles('South', 2)
    intersection.update_waiting_vehicles('East', 8)
    intersection.update_waiting_vehicles('West', 1)

    # Run the simulation for 60 seconds
    intersection.run_simulation(60)

Big(O) Analysis

Time Complexity

O(1) – The core logic involves regularly checking waiting vehicles for each direction, which we can assume is a fixed number (e.g., North, South, East, West). Determining the direction with the longest wait or most vehicles involves comparing a fixed set of values. Switching lights and implementing time limits also take constant time. Therefore, the overall time complexity is O(1) because the operations do not scale with any input size.

Space Complexity

O(1) – The primary auxiliary space used in this simulation involves tracking waiting vehicles for each direction and potentially storing emergency vehicle detection status. Assuming a fixed number of directions (e.g., North, South, East, West), the space required to store waiting times or vehicle counts for each direction remains constant, regardless of the overall traffic volume. Similarly, emergency vehicle detection would likely involve a boolean flag or a small, fixed-size data structure. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
No cars approaching the intersection from any direction	The traffic lights should remain in their default state, perhaps alternating green periodically to prevent indefinite waits on other directions.
Cars approaching from all directions simultaneously	The algorithm must prioritize or use a predefined order to handle simultaneous requests to ensure fairness and prevent starvation.
One direction has a continuous stream of cars while others have none	Implement a maximum green light duration to prevent one direction from monopolizing the intersection and starving other directions.
A car arrives right as the light turns red for its direction	The algorithm should have a grace period or minimum red duration to prevent constant switching if a car arrives immediately after the light changes.
Integer overflow when calculating wait times or durations	Use appropriate data types (e.g., long) to prevent overflow or implement checks to handle potential overflows gracefully.
Emergency vehicle approaching the intersection	The system should have a mechanism to immediately switch the lights to allow the emergency vehicle to pass safely, potentially interrupting normal cycling.
Malfunctioning sensor reporting incorrect car counts	Implement sanity checks and fallback mechanisms (e.g., using historical data or fixed timings) to handle unreliable sensor data.
System receives conflicting signals from multiple sensors	Implement a conflict resolution strategy, such as prioritizing data from more reliable sensors or using a weighted average of sensor readings.

No cars approaching the intersection from any direction

How to Handle:

The traffic lights should remain in their default state, perhaps alternating green periodically to prevent indefinite waits on other directions.

Cars approaching from all directions simultaneously

How to Handle:

The algorithm must prioritize or use a predefined order to handle simultaneous requests to ensure fairness and prevent starvation.

One direction has a continuous stream of cars while others have none

How to Handle:

Implement a maximum green light duration to prevent one direction from monopolizing the intersection and starving other directions.

A car arrives right as the light turns red for its direction

How to Handle:

The algorithm should have a grace period or minimum red duration to prevent constant switching if a car arrives immediately after the light changes.

Integer overflow when calculating wait times or durations

How to Handle:

Use appropriate data types (e.g., long) to prevent overflow or implement checks to handle potential overflows gracefully.

Emergency vehicle approaching the intersection

How to Handle:

The system should have a mechanism to immediately switch the lights to allow the emergency vehicle to pass safely, potentially interrupting normal cycling.

Malfunctioning sensor reporting incorrect car counts

How to Handle:

Implement sanity checks and fallback mechanisms (e.g., using historical data or fixed timings) to handle unreliable sensor data.

System receives conflicting signals from multiple sensors

How to Handle:

Implement a conflict resolution strategy, such as prioritizing data from more reliable sensors or using a weighted average of sensor readings.