一个经典的贪心问题，求解答

Question

-

样例过了，但是有数据点没过，不知道错哪了
#include<bits/stdc++.h>
using namespace std;

vector<vector<int> > arr;

void storage(int n){
    if(n==0) return;
    int beginTime,endTime;
    for(int i=0;i<n;i++){
        vector<int> arr1;//定义在循环里面 
        cin>>beginTime>>endTime;
        arr1.push_back(beginTime);
        arr1.push_back(endTime);
        arr.push_back(arr1);
    }
}

bool cmp(vector<int>&a,vector<int>&b){
    return a[0]<b[0];
}

int maxTime(int n){
    if(n==0) return 0;
    sort(arr.begin(),arr.end(),cmp);
    int res=1;
    int curTime=arr[0][1];
    for(int i=1;i<arr.size();i++){
        if(curTime<=arr[i][0]){
            res++;
            curTime=arr[i][1];
        }
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    storage(n);
    int res=maxTime(n);
    cout<<res;
    cin.get();
    return 0;
}

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

你的代码逻辑大体上是正确的，但是有一个小问题可能导致数据点没过。在你的 maxTime 函数中，当计算最大比赛数量时，你是按照比赛开始时间排序的，然后在遍历比赛列表时检查当前比赛的结束时间是否在当前时间之前。然而，如果在比赛列表中有两个或多个比赛的开始时间相同，那么它们应该被视为可以同时进行的比赛。因此，你应该在排序时同时考虑开始时间和结束时间。这样，如果两个比赛的开始时间相同，那么结束时间较晚的比赛应该排在前面。你可以修改 cmp 函数以同时考虑这两个因素：先比较开始时间，如果开始时间相同，则比较结束时间。以下是修改后的代码：

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> arr;

void storage(int n){
    for(int i = 0; i < n; i++){
        int beginTime, endTime;
        cin >> beginTime >> endTime;
        arr.push_back({beginTime, endTime});  // 使用初始化列表语法直接初始化向量
    }
}

bool cmp(const vector<int>& a, const vector<int>& b){  // 修改比较函数以同时考虑开始和结束时间
    if (a[0] == b[0]) return a[1] > b[1];  // 如果开始时间相同，则按照结束时间排序
    return a[0] < b[0];  // 按照开始时间排序
}

int maxTime(int n){
    sort(arr.begin(), arr.end(), cmp);  // 按照修改后的比较函数排序比赛列表
    if (arr.empty()) return 0;  // 比赛列表为空时返回 0
    int res = 1;  // 记录参加的比赛数量，初始值为 1（至少参加一个自己的开幕式）
    int curTime = arr[0][1];  // 记录当前时间，初始值为第一个比赛的结束时间
    for (int i = 1; i < arr.size(); i++){  // 遍历剩余的比赛列表
        if (curTime <= arr[i][0]){  // 如果当前时间小于等于下一个比赛的开始时间，则可以参加下一个比赛
            res++;  // 参加比赛数量加一
            curTime = arr[i][1];  // 更新当前时间为下一个比赛的结束时间
        }
    }
    return res;  // 返回参加的最大比赛数量
}

int main(){
    int n;
    cin >> n;  // 输入比赛数量
    storage(n);  // 存储比赛信息
    cout << maxTime(n);  // 输出最多参加的比赛数量
    return 0;
}

这样的修改应该可以解决你的问题。