Domain 1EasyCORE

Traffic Light Controlled Intersection

The problem involves designing a traffic light control system for an intersection with two roads. Cars arrive at the intersection from different directions and need to cross safely without causing deadlocks. The traffic lights on each road can be either green or red, but they cannot both be green simultaneously.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 1

1279. Traffic Light Controlled Intersection

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 76.2%


Problem Breakdown

The problem involves designing a traffic light control system for an intersection with two roads. Cars arrive at the intersection from different directions and need to cross safely without causing deadlocks. The traffic lights on each road can be either green or red, but they cannot both be green simultaneously.

Inputs:

  • carId: Unique identifier for each car.
  • roadId: Identifier for the road the car is traveling on (1 or 2).
  • direction: Direction of travel for the car (1 to 4).
  • turnGreen: Function to turn the traffic light green on the current road.
  • crossCar: Function to allow the car to cross the intersection.

Outputs:

  • The function should ensure that cars from different roads do not cross simultaneously, avoiding deadlocks. It should also handle the transition of the traffic light between roads correctly.

Implicit Constraints/Edge Cases:

  • Initially, the traffic light is green on road A and red on road B.
  • If a car arrives on a road where the light is already green, it can cross immediately.
  • If a car arrives on a road where the light is red, the light must turn green before the car can cross.

Intuition

A brute-force approach would involve checking each car’s arrival and manually managing the traffic lights. However, this would be inefficient and error-prone due to potential deadlocks and race conditions.

The key insight is to use a mutex (or lock) to ensure that only one road has its light green at any given time. This prevents cars from different roads from crossing simultaneously, thus avoiding deadlocks.

Approach

  1. Mutex Initialization: Use a mutex to control access to the traffic light.
  2. Car Arrival Handling:
    • Acquire the lock when a car arrives.
    • Check if the current road’s light is green.
    • If not, turn the light green for the current road using turnGreen.
    • Allow the car to cross the intersection using crossCar.
    • Release the lock after the car has crossed.

This approach ensures that only one road can have its light green at any time, preventing cars from different roads from crossing simultaneously.

Complexity Analysis

  • Time Complexity: O(1) for each car’s arrival and handling. The mutex operations are assumed to be constant time.
  • Space Complexity: O(1), as we only use a single mutex for synchronization.

Solution

import threading

class TrafficLight:
    def __init__(self):
        self.lock = threading.Lock()
        self.current_green_road = 1  # Initially, road A is green

    def carArrived(
        self,
        carId: int,                      # ID of the car
        roadId: int,                     # ID of the road the car travels on. Can be 1 (road A) or 2 (road B)
        direction: int,                  # Direction of the car
        turnGreen: 'Callable[[], None]', # Use turnGreen() to turn light to green on current road
        crossCar: 'Callable[[], None]'   # Use crossCar() to make car cross the intersection
    ) -> None:
        
        with self.lock:
            if self.current_green_road != roadId:
                turnGreen()
                self.current_green_road = roadId
            
            crossCar()

Edge Cases Handled

  • Initial State: The traffic light starts green on road A, as specified.
  • Concurrent Cars: Multiple cars arriving simultaneously are handled by the mutex, ensuring that only one car crosses at a time.
  • Light Transition: If a car arrives on a road with a red light, the light is turned green before the car crosses.
  • Single Road Traffic: If all cars arrive from the same road, they can cross without any light transitions.