本题用到了贪心 我是先进行排序 把同时间开始但最早结束的
订单放在前面
算法1
(贪心)
时间复杂度
C++ 代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int l;
int r;
}a[500005];
bool cmp(node c,node b)
{
return c.r<b.r; //谁结束的早这在前面
if(c.r==b.r)
{
return c.l<b.l; //同时结束 就比较开始时间
}
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i].l>>a[i].r;
}
sort(a,a+n,cmp);
int num=1,s; //s为上一笔订单的结束时间 初始化s=最早结束时间
s=a[0].r;
for(int i=1;i<n;i++)
{
if(a[i].l>s) //如果下一笔订单是开始时间>上一笔结束时间 num++
{
num++;
s=a[i].r;
}
}
cout<<num;
return 0;
}