题意及思路

  • 题意：找寻最多能参加比赛的个数。😉题目约束见上图。
  • 思路：这题做法就是区间贪心😄。一开始的做法是是🙄先排序，规则是先按起始时间从小到大排，如果起始时间相同则按结束时间从小到大排。然后选择满足约束条件的区间即可。但是这种想法有些局限。举例说明：对于下列案例

答案是5个，但是直接从前往能后搜索只能得到3。原因是因为如果选择了长区间，后面可选择的情况就变少了，例如下图中，如果选择了[0,3]区间，那么后续的[2,4]区间就无法选择。所以我们贪心的策略是，在满足约束的情况下，先选择当前区间，如果下次遇到当前区间的子区间的话，再重置选择区间即可。


  • 解释：下面代码中， 
int ans = 1,last_end = cts[0].e;
last_end表示上一次选择的区间结束位置，即比赛结束时间。

代码 

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+5;

struct ct{
    int s,e;
}cts[N];

bool cmp(ct a,ct b){
    if(a.s!=b.s) return a.s < b.s;
    else return a.e < b.e;
}

int main()
{ std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
    	cin >> cts[i].s >> cts[i].e;
    }
    sort(cts,cts+n,cmp);
    
    int ans = 1,last_end = cts[0].e;
    for(int i=1;i<n;i++){
    	if(cts[i].e<=last_end){
    	    last_end = cts[i].e;
	    continue;
	} 
    	if(cts[i].s>=last_end){
    	    last_end = cts[i].e;
            ans++;
	}
    }
    cout << ans << endl;
    
    return 0;
}