【错题集-编程题】活动安排(贪心 - 区间)

简介: 【错题集-编程题】活动安排(贪心 - 区间)

牛客对应题目链接:活动安排_牛客题霸_牛客网 (nowcoder.com)


一、分析题目

区间问题的贪心:排序,然后分情况讨论,看看是合并还是求交集。


二、代码

1、没看题解之前AC的代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> PII;
vector<PII> q;
 
bool cmp(PII x, PII y)
{
    return x.second<y.second;
}
 
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        q.push_back({a, b});
    }
    sort(q.begin(), q.end(), cmp);
    int cnt=1;
    int ed=q[0].second;
    for(int i=1; i<q.size(); i++)
    {
        if(ed<=q[i].first)
        {
            cnt++;
            ed=q[i].second;
        }
    }
    cout << cnt << endl;
    return 0;
}

2、值得学习的代码

//写法一
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 2e5 + 10;
 
int n;
PII arr[N];
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i].first >> arr[i].second;
    sort(arr, arr + n);
 
    int ret = 0, r = arr[0].second;
    for(int i = 1; i < n; i++)
    {
        if(arr[i].first < r) // 有重叠
        {
            r = min(r, arr[i].second);
        } 
        else // 没有重叠
        {
            ret++;
            r = arr[i].second;
        }
    }
    cout << ret + 1 << endl;
 
    return 0;
}
 
//写法二
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N=2e5+10;
 
struct activity
{
    int a;
    int b;
    static bool cmp(const activity& v1, const activity& v2)
    {
        return v1.b<v2.b;
    }
}ac[N];
 
int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> ac[i].a >> ac[i].b;
    sort(ac, ac+n, activity::cmp);
    int cnt=1;
    int ed=ac[0].b;
    for(int i=1; i<n; i++)
    {
        if(ed<=ac[i].a)
        {
            cnt++;
            ed=ac[i].b;
        }
    }
    cout << cnt << endl;
    return 0;
}

三、反思与改进

对手写 cmp 排序还不够熟悉,需要多尝试不同写法并牢记。


目录
打赏
0
0
0
0
9
分享
相关文章
最全MySQL面试60题(含答案):存储引擎+数据库锁+索引+SQL优化等
最全MySQL面试60题(含答案):存储引擎+数据库锁+索引+SQL优化等
1775 0
已解决 BrokenPipeError: [Errno 32] Broken pipe
已解决 BrokenPipeError: [Errno 32] Broken pipe
8295 0
已解决 BrokenPipeError: [Errno 32] Broken pipe
【错题集-编程题】主持人调度(一)(排序)
【错题集-编程题】主持人调度(一)(排序)
【错题集-编程题】主持人调度(二)(贪心 + 优先级队列)
【错题集-编程题】主持人调度(二)(贪心 + 优先级队列)
ECS使用体验
使用阿里云也很省心。不需要花时间维修服务器硬件,有阿里监控服务器,也很稳定,不会出现异常关机等掉线状况。阿里云服务器非常安全,不会出现安全问题。能愿意花钱投入资金给我们这些穷学生一个免费使用的机会,也是很良心啦。用了好几天我差点忘了这事情,然后阿里还会发短信提示我服务器要到期了,短信看过之后忘了,工作人员直接打电话联系我。服务还是很贴心的,不然我自己可能记不住时间,万一过期了都不知道。感觉整个流程使用下来,体验还是不错的。如果以后有需要,自己也会选择继续使用阿里云的服务器。以后的工作什么遇到有需要的,阿里云服务器也是一个不错的选择。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问