Hotel Bookings Possible C from InterviewBit website. I've been working on it and I couldnt find a solution for it. The question is: A hotel manager has to process N advance bookings of rooms for the next season. His hotel has C rooms. Bookings contain an arrival date and a departure date. He wants to find out whether there are enough rooms in the hotel to satisfy the demand. Write a program that solves this problem in time O(N log N) .

Input Format First argument is an integer array A containing arrival time of booking.

Second argument is an integer array B containing departure time of booking.

Third argument is an integer C denoting the count of rooms.

Output Format Return True if there are enough rooms for N bookings else return False.

Return 0/1 for C programs.

Code:

bool Solution::hotel(vector<int> &arrive, vector<int> &depart, int K) {
     vector<pair<int,int> >v;
    int n=arrive.size();
    for(int i=0;i<n;i  ){
        v.push_back(make_pair(arrive[i],1));
        v.push_back(make_pair(depart[i],-1));
    }
    sort(v.begin(),v.end());
    int count=0;
    for(int i=0;i<2*n;i  ){
        count =v[i].second;
        if(count>K)
         return false;
    }
    return true;
}

and Im getting error for just this test case

Your submission failed for the following input
A : [ 1, 2, 3 ]
B : [ 2, 3, 4 ]
C : 1

The expected return value: 
0
Your function returned the following: 
1

Someone help!

CodePudding user response：

You're processing departures before arrivals.

In the sample test case, someone stays from days 1~2. That means, the room is occupied on day 2; and is only vacated on day 3. For some departure date x, you should process it on x 1 as that's when the guest leaves.

So, you can simply update this loop:

for(int i=0;i<n;i  ){
        v.push_back(make_pair(arrive[i],1));
        v.push_back(make_pair(depart[i],-1));
}

to:

for(int i=0;i<n;i  ){
        v.push_back(make_pair(arrive[i],1));
        v.push_back(make_pair(depart[i] 1,-1));
}