Assign Cab Requests

Question

Given n cabs and a stream of incoming requests of cab booking with start time and end time (in HH:MM:SS format) of the booking. Find which booking should be routed to which cab.

Input

n=3

Requests

08:30:00 10:30:00

10:00:00 11:00:00

10:45:00 11:00:00

10:40:00 11:00:00

Output

Note : The booking requests are stream of inputs which are not sorted

Solution

We need to store the history of cab requests picked by the corresponding cab so that we can decide on future requests.
To store the history we can use a vector< set< int > > , where the index represents the cabId and value represents the set of startTime of the request history of the cab.
We need to also store the corresponding endTime for every startTime to check for overlap, which we can store using vector< map < int,int > > , where each entry i of vector, stores the startTime, endTime in form of a map for that particular cab i.

Whenever a new cab request of startTime-endTime comes we need to check the following :

  -  For every cab i, check the position of the incoming startTime in the set of startTimes.
  -  Check the startTime of the next cab if it is less than the incoming endTime (to check for overlap).
  -  Check the lastTime of the previous request of cab obtained using binary search, to see if the 
      request can be taken by the cab(there is no overlap).
  - If the cab request can be taken by cab i, insert the startTime into the set and the map of startTime, endTime.
  - If cab request cannot be taken by cab i, check for cab (i+1).

Code


vector<map<int,int> > assignCab(int n, string startTimeString, string endTimeString ){
    int startTime = convertToInt(startTimeString);
    int endTime = convertToInt(endTimeString);
    vector<map<int,int> > cabTrips(n);
    vector<set<int> > cabTripStartTimes;
    int  cabIndex=-1;
    for(int i=0;i<cabTrips.size();i++){
        if(cabTrips[i].find(startTime)!=cabTrips[i].end()){
            continue;
        }
        if( cabTripStartTimes.size()==0){
           cabIndex=i;
           break;
        }
        else if(startTime<*(cabTripStartTimes.begin() && endTime<=*(cabTripStartTimes.begin()){
            cabIndex=i;
            break;
       }
        else{
            auto it =cabTripStartTimes.lower_bound(starTime);
            int prevValue = *(--it);
            int nextValue = *it; 
            if(cabTripStartTimes[i][prevValue]<=startTime && endTime<=nextValue){
                cabIndex=i;
                break;
           }
        } 
    }
    if(cabIndex==-1){
        cout<<"Not possible to assign all cabs";
        return -1;
    }
    else{
        cabTripStartTimes[cabIndex].insert(startTime);
        cabTrips[cabIndex][startTime]=endTime;
    }
    return cabTrips;
}

CodeMinion