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

1

2

1

3

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;
}