贪心算法 整数区间

【例8】整数区间

题目要求：

请编程完成以下任务：

1. 读取闭区间的个数及它们的描述；

2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。

【输入】

首行包括区间的数目n,1<=n<=10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0<=a<=b<=10000,它们是某一个区间的开始值和结束值。

【输出】

第一行集合元素的个数,对于每一个区间都至少有一个整数属于该区间,且集合所包含元素数目最少。

【样例输入】

4

3 6

2 4

0 2

4 7

【样例输出】

2

题意说明：

这题比较难理解，题意为就是你选n个数，保证你输入区间在这n个数至少有一个符合

算法分析：

•算法模型：给n个闭区间[ai,bi], 在数轴上选尽量少的点,使每个区间内至少有一个点。

•算法：首先按b1<=b2<=...<=bn排序。每次标记当前区间的右端点x，并右移当前区间指针（判断x是否大于左端点），直到当前区间不包含x,再重复上述操作。

•如下图，如果选灰色点，移动到黑色点更优。

代码实现：

#include<bits/stdc++.h>
using namespace std;
struct range
{
  int from,to;              //from开始，to结束
}a[10000];
 bool cmp(range x,range y)   //按结束排序
 {
     return x.to<y.to;
 }
 int main()
 {
     int n,i,sum=0;
     cin>>n;
     for(i=0;i<n;i++)
        cin>>a[i].from>>a[i].to;
     sort(a,a+n,cmp);
     int x;
     for(i=0,x=-1;i<n;i++)          //初始x的值，保证当下永远小于任意左端点
     {                              //令x=-1可以使第一个区间与其他区间的操作相同。

         if(x>=a[i].from)   continue;   //判断上一个右端点是否大于左端点，如果大于则则肯定包含标记号
         x=a[i].to;                     //更新标记点
         sum++;        
     }
     cout<<sum;
     return 0;
 }