题目背景

Python 用户可以尝试使用 pypy3 提交试题。

快 noip 了，yyy 很紧张！

题目描述

现在各大 oj 上有 n 个比赛，每个比赛的开始、结束的时间点是知道的。

yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 2 个及以上的比赛。

输入格式

第一行是一个整数 n，接下来 n 行每行是 2 个整数 ai​,bi​ (ai​<bi​)，表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

输入输出样例

输入 #1复制

3
0 2
2 4
1 3

输出 #1复制

2

说明/提示

• 对于 20% 的数据，n≤10；
• 对于 50% 的数据，n≤103；
• 对于 70% 的数据，n≤105；
• 对于 100% 的数据，1≤n≤106，0≤ai​<bi​≤106。

解题思路：

• 首先，我的思路是构造一个关于比赛的结构体，包括开始时间和结束时间，并按照开始时间进行排序（自己写一个compare函数），然后遍历数组依次选择开始时间最早且时间未被覆盖的比赛。但很快发现问题，每次选择开始时间最早的比赛，万一有一个比赛的开始时间很早，但是持续时间很长，把后续的时间都覆盖了，其他的比赛不能进行，而该比赛只能让结果+1,显然不是最优解。
• 后续参考了题解里一位大佬的思路，以及deepseek的回答。按照结束时间最早进行排序，后续依次选择时间未被覆盖的比赛。虽然我已经明白了我之前的思路不是最优解，但这个思路为什么是最优解呢？因为每次选择结束时间最早的比赛，在能力范围之内最大限度地保证了后续能容纳的比赛数量（这么说好像懂了），即贪心算法的思想。

AC代码：

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

struct compeT {
	int st;
	int en;
};

//按照结束时间进行升序排序
bool compare(const compeT &a, const compeT &b) {
	return a.en < b.en;
}

int main() {
	int n;
	cin >> n;
	compeT arr[n];
	int x, y;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		arr[i].st = x;
		arr[i].en = y;
	}
	sort(arr, arr + n, compare);
	int ans=1;
    int j=arr[0].en;//前一场结束时间
    int i=1;
    while(i<n)
        {
            if(arr[i].st>=j)
            {
                ans++;
                j=arr[i].en;
                //i++;
            }
            i++;
        }
    cout << ans;
	return 0;
}