C7-E 复习安排

题目描述

猫猫即将开始紧张刺激的考期！

考期总共有 nn 天，猫猫有$ k$ 门课需要考试。对于第 i 门课，如果想顺利通过考试，必须在考期的第 lil_i 天到第 rir_i 天全身心投入这门课的复习，不能复习其他课程，否则就会挂科。

猫猫最多能通过多少门课的考试呢？

输入

本题测试点包含多组数据。

第一行，一个正整数 T（1≤T≤5）T（1≤T≤5），表示数据组数。

对于每组数据：

第一行，两个正整数 n,k（1≤n≤105，1≤k≤n）n,k（1≤n≤10^5，1≤k≤n），分别表示考期天数和课程数。

接下来 $k $行，每行两个正整数 li,ri（1≤li≤ri≤n）l_i,r_i（1≤l_i≤r_i≤n），表示通过第 i 门课的考试所需的复习起讫天数。

输出

对于每组数据：

输出一行，一个整数，表示最多能通过的考试数量。

输入样例

1
2
3
4
5
6
7
8
9
10
2
8 4
1 1
2 4
4 5
6 8
5 3
1 3
2 4
3 5

输出样例

1
2
3
1

提示

对于样例中第一组数据，选择复习第 1,3,4 门课，对应在考期的第 1 天、第 4∼5 天、第 6∼8 天复习这些课程，最多能通过 3 门课的考试。

题目分析

贪心算法，优先选择结束时间早的复习安排。之后模拟即可。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b)
{
    return a.second < b.second;
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, k;
        cin >> n >> k;
        vector<pair<int, int>> a;
        for (int i = 0; i < k; i++)
        {
            int l, r;
            cin >> l >> r;
            a.push_back({l, r});
        }
        sort(a.begin(), a.end(), cmp);
        int ans = 0;
        int t = 0;
        for (int i = 0; i < k; i++)
        {
            if (a[i].first > t)
            {
                ans++;
                t = a[i].second;
            }
        }
        cout << ans << endl;
    }

    return 0;
}