贪心6--整数区间

一、心得

 

二、题目和分析

 给n个区间，形式为[a, b]，a和b均为整数，且a < b。

求一个最小的整数点的集合，使得每个区间至少2个不同的元素(整数点)属于这个集合。

求这个集合的元素个数。

输入

第1行：1个整数n(1 <= n <= 10000)

接下来n行，每行2个整数，表示区间的左右端点a, b(0 <=a < b <= 10000)

输出

第1行：1个整数，表示集合的元素的个数

样例输入

4

3 6

2 4

0 2

4 7

样例输出

4

三、代码和结果

 

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 struct act{ 5     int begin; 6     int end; 7 }; 8  9 int mycmp(const act &a,const act &b){10     return a.end
       
        >n;18     act a[1005];19     for(int i=1;i<=n;i++){20         cin>>a[i].begin>>a[i].end;21     }22     sort(a+1,a+n+1,mycmp);23     cout<<"排序后的序列"<
        
         x){33             total++;34             x=a[i].end;35             ans[total]=x;36         }37     38     }39     cout<<"ans："<
         
          <