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

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

题目描述:

好吧。这道题的目的在于让大家认识贪心问题的三个区间经典问题：区间选点问题，区间覆盖问题，以及该题的选择不相交区间问题。有许多的贪心问题可以转化为这三类的问题。

那么，对于该问题。就是给一系列的区间，求最多的区间，要求区间个数最多，这些区间不相交，需要注意的是这些区间都是闭区间。

输入描述:

第一行一个数n为区间个数(n<=1000)接下来有n行，每行有两个数a，b分别为区间的两个端点,a,b在int范围。EOF结尾。

输出描述:

输出如样例所示。

样例输入:

2

1 10

10 11

3

1 10

10 11

11 20

样例输出:

Case 1:

1.

Case 2:

2.

解题思路:

选择不相交区间问题：贪心思想，先按b从小到大进行排序，再选择b0作为选点temp，如果出现ai>temp，则以bi作为temp，再按照这样的方式迭代，直至所有区间遍历完。这道题有点坑，输入的时候要判断两个端点的大小。

#include 
   
    #include 
    
     using namespace std;struct edge {	int l, r;}e[1010];int cmp(edge a, edge b){	return a.r < b.r;}int main(){	int t = 1, n, ans, temp;	while (cin >> n)	{		ans = 1;		for (int i = 0; i < n; i++)		{			cin >> e[i].l >> e[i].r;			if (e[i].l > e[i].r)				swap(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 << "Case " << t++ << ":\n" << ans << ".\n";	}	return 0;}
    
   

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