InterviewBit中Hotel Bookings Possible问题C++解法报错求助

错误原因 #

你的代码核心逻辑正确，但事件排序规则不符合题目隐含的日期定义。题目中，当入住日期与另一笔订单的退房日期相同时，这两个订单的住宿时间段是重叠的（即退房客人在当日仍占用房间，新客人当日入住需要额外房间）。但默认的pair排序会将日期相同的退房事件（(date, -1)）排在入住事件（(date, 1)）之前，导致计算的房间占用数未达到实际峰值，从而错误返回true。

以失败的测试用例为例：

• 原事件对：(1,1), (2,-1), (2,1), (3,-1), (3,1), (4,-1)
• 默认排序后先处理(2,-1)再处理(2,1)，房间占用数变化为1→0→1，始终未超过K=1，错误返回true
• 但实际按题目规则，这两个事件应视为重叠，需先处理入住事件，房间占用数会变为1→2，超过K=1，应返回false

修复后的代码 #

需要自定义排序规则：当事件日期相同时，让入住事件（second=1）排在退房事件（second=-1）之前。

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(), [](const pair<int,int>& a, const pair<int,int>& b) {
        if(a.first == b.first) {
            return a.second > b.second; // 1 > -1，所以入住事件排在前面
        }
        return a.first < b.first;
    });
    int count = 0;
    for(int i=0; i<2*n; i++){
        count += v[i].second;
        if(count > K)
            return false;
    }
    return true;
}

验证修复 #

修改排序规则后，测试用例的事件顺序变为：
(1,1), (2,1), (2,-1), (3,1), (3,-1), (4,-1)
房间占用数变化：1→2（此时超过K=1），直接返回false，符合预期结果。

内容的提问来源于stack exchange，提问作者VishnuKc