题目传送门
这道题就是贪心中的经典区间覆盖问题,先用右端点从小到大排序目的是先进行时间少的订单,然后用贪心算法进行计算:循环判断:
最后输出最大接受订单数
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; struct Node{ int s; //订单开始时间 int e; //订单结束时间 }a[500010]; bool cmp(Node a,Node b){ return a.e<b.e; //右端点从小到大排序 } int ans; //计数器 int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i].s>>a[i].e; sort(a+1,a+n+1,cmp); int now_time=-1; //时间可以从 0 开始,当前时间要初始化成 -1 for(int i=1;i<=n;i++){ if(a[i].s>now_time){ //如果订单开始时间和当前时间不重复,就可以接受订单 ans++; //符合条件就计数器累加 now_time=a[i].e; } } cout<<ans<<endl; //最后输出可以接受的最大订单数 return 0; }