Implement Four way stop


  • 1
    S

    interface FourWayStop {
    /** Adds a car to the intersection. This does not mean the car gets to the stop line. /
    void add(int carId, int roadId);
    /
    * Returns the ID of the car to cross the intersection next. Removes the car. */
    int remove();
    }

    Let us simulate four way stop scenario and implement those two methods.


  • 0
    A

    @Sara can maintain the queue of cars coming to intersection. Whats the use of roadId?


  • 0
    T

    Hi , here is my solution,
    using two list, one is for carid, one is for roadid for each car in car list.
    eachtime adding new car, will calculate an index.

    public class StopSign : FourWayStop {
    
        // 0 : up
        // 1: right
        // 2: down
        // 3: left
        private int[] indexs = new int[4];
    
        private List<int> queue = new List<int>();
        private List<int> indexQueue = new List<int>();
    
        public void add(int carId, int roadId)
        {
            int index = 0;
            for(int i = 0;i<4;i++){
                if(i == roadId){
                    index+=indexs[i]*4;
                }else if(indexs[i] < indexs[roadId]){
                    index-= indexs[roadId] - indexs[i];
                }else if(indexs[i] > indexs[roadId]){
                    index++;
                }
            }
            indexs[roadId]++;
            queue.Insert(index,cardId);
            indexQueue.Insert(index,roadId);
        }
    
        public int remove()
        {
            if(queue.Count ==0 )
                return -1;
    
            int returnVal = queue[0];
    
            indexs[indexQueue[0]]--;
            queue.RemoveAt(0);
            indexQueue.RemoveAt(0);
            return returnVal;
        }
    

    }
    ...


  • 4
    H
    class FourWayStop {
      // roadQ record the next roadId to be available
      list<int> roadQ;
      // carQ record the cars on each road
      list<int> carQ[4];
    public:
      // Adds a car to the intersection. This does not mean the car gets to the stop line. 
      void add(int carId, int roadId) {
        // if car pull up to the front, this road enters roadQ
        if (carQ[roadId].empty()) {
          roadQ.push_back(roadId);
        }
        // this car enters carQ of the road
        carQ[roadId].push_back(carId);
      }
      // Returns the ID of the car to cross the intersection next. Removes the car. 
      int remove() {
        if (roadQ.empty()) return 0;
        // get the first road in roadQ
        int road = roadQ.front();
        roadQ.pop_front();
        // the first car in the first road pass intersection
        int car = carQ[road].front();
        carQ[road].pop_front();
        // if there is a next car in this road, this road enters roadQ
        if (!carQ[road].empty()) roadQ.push_back(road);
        return car;
      }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.