本文共 879 字，大约阅读时间需要 2 分钟。

• 内存限制:64MB 时间限制:2000ms

题目描述:

上数学课时，老师给了LYH一些闭区间，让他取尽量少的点，使得每个闭区间内至少有一个点。但是这几天LYH太忙了，你们帮帮他吗？

输入描述:

多组测试数据。每组数据先输入一个N，表示有N个闭区间（N≤100)。接下来N行，每行输入两个数a，b(0≤a≤b≤100），表示区间的两个端点。

输出描述:

输出一个整数，表示最少需要找几个点。

样例输入:

4

1 5

2 4

1 4

2 3

3

1 2

3 4

5 6

1

2 2

样例输出:

1

3

1

解题思路:

区间选点问题：贪心思想，先按b从小到大进行排序，再选择b0作为选点temp，如果出现ai>temp，则以bi作为temp，再按照这样的方式迭代，直至所有区间遍历完。

#include 
   
    #include 
    
     using namespace std;struct edge {    int l, r;}e[110];int cmp(edge a, edge b){    return a.r < b.r;}int main(){    int t, n, ans, temp;    while (cin >> n)    {        ans = 1;        for (int i = 0; i < n; i++)            cin >> e[i].l >> e[i].r;        sort(e, e + n, cmp);        temp = e[0].r;        for (int i = 1; i < n; i++)        {            if (e[i].l > temp)            {                ans++;                temp = e[i].r;            }        }        cout << ans << endl;    }    return 0;}
    
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/84072218 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！