1279. Traffic Light Controlled Intersection

leetcode easy

#csharp#easy#leetcode

Task

Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный.

Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль.

direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом.

Пример:

Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]

Output: [

"Car 1 Has Passed Road A In Direction 2", // Traffic light on road A is green, car 1 can cross the intersection.

"Traffic Light On Road B Is Green", // Car 2 requests green light for road B.

"Car 2 Has Passed Road B In Direction 4", // Car 2 crosses as the light is green on road B now.

"Car 3 Has Passed Road B In Direction 3", // Car 3 crosses as the light is green on road B now.

"Traffic Light On Road A Is Green", // Car 5 requests green light for road A.

"Car 5 Has Passed Road A In Direction 1", // Car 5 crosses as the light is green on road A now.

"Traffic Light On Road B Is Green", // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.

"Car 4 Has Passed Road B In Direction 3" // Car 4 crosses as the light is green on road B now.

]

C# solution

matched/original

using System;
using System.Threading;
public class TrafficLight {
    private int greenRoad = 1;
    private readonly object lockObj = new object();
    public void CarArrived(
        int carId,
        int roadId,
        int direction,
        Action turnGreen,
        Action crossCar
    ) {
        lock (lockObj) {
            if (greenRoad != roadId) {
                turnGreen();
                greenRoad = roadId;
            }
            crossCar();
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TrafficLight {
    private int greenRoad = 1;
    private readonly object lockObj = new object();
    public void CarArrived(
        int carId,
        int roadId,
        int direction,
        Action turnGreen,
        Action crossCar
    ) {
        lock (lockObj) {
            if (greenRoad != roadId) {
                turnGreen();
                greenRoad = roadId;
            }
            crossCar();
        }
    }
}

Java solution

matched/original

import java.util.concurrent.locks.*;

public class TrafficLight {
    private int greenRoad = 1;
    private final Lock lock = new ReentrantLock();

    public void carArrived(
        int carId,
        int roadId,
        int direction,
        Runnable turnGreen,
        Runnable crossCar
    ) {
        lock.lock();
        try {
            if (greenRoad != roadId) {
                turnGreen.run();
                greenRoad = roadId;
            }
            crossCar.run();
        } finally {
            lock.unlock();
        }
    }
}

Go solution

matched/original

package main

import "sync"

type TrafficLight struct {
    greenRoad int
    mu        sync.Mutex
}

func NewTrafficLight() *TrafficLight {
    return &TrafficLight{greenRoad: 1}
}

func (tl *TrafficLight) CarArrived(
    carId int,
    roadId int,
    direction int,
    turnGreen func(),
    crossCar func(),
) {
    tl.mu.Lock()
    defer tl.mu.Unlock()
    if tl.greenRoad != roadId {
        turnGreen()
        tl.greenRoad = roadId
    }
    crossCar()
}

Explanation

Algorithm

Если на дороге, по которой едет автомобиль, уже зеленый свет, вызываем функцию crossCar.

Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar.

Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков

😎