貪心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 <iostream> 2 #include <algorithm> 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<b.end; 11 } 12 13 //貪心，選最快結束就好 14 int main(){ 15 //freopen("in.txt","r",stdin); 16 int n; 17 cin>>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<<"排序后的序列"<<endl; 24 for(int i=1;i<=n;i++){ 25 cout<<a[i].begin<<" "<<a[i].end<<endl; 26 } 27 int total=1; 28 int x=a[1].end; 29 int ans[1005]; 30 ans[total]=x; 31 for(int i=2;i<=n;i++){ 32 if(a[i].begin>x){ 33 total++; 34 x=a[i].end; 35 ans[total]=x; 36 } 37 38 } 39 cout<<"ans："<<total<<endl; 40 for(int i=1;i<=total;i++){ 41 cout<<ans[i]<<" "; 42 } 43 cout<<endl; 44 45 return 0; 46 }

轉載于:https://www.cnblogs.com/Renyi-Fan/p/7135615.html

總結

以上是生活随笔為你收集整理的贪心6--整数区间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。