【贪心】区间选点
【题目描述】
数轴上有n个闭区间[ai, bi]，取尽量少的点，使得每个区间内都至少有一个点。（不同区间内含的点可以是同一个，1<=n<=10000，1<=ai<=bi<=10^9）。求最少点的个数。
【输入】
n
n项工作的开始与结束时间
【输出】
最多参与的工作项数
【输入样例1】
4 3 13 6 20 4 14 1 10
【输出样例1】
1
【输入样例2】
3 4 7 6 8 11 20
【输出样例2】
2
【题目原型分析】
参考下图模型：
或者下图这种模型：
关于至少有一个点的解释：如果区间i内已经有一个点被取到，则称此区间已经被满足（闭区间）。
【解题思路】
首先考虑如果两个区间一个区间包含另外一个，小区间内的点一定在大区间内，但是大区间内的点不一定在小区间内。所以此时，只需要考虑较小的区间。当两个区间不包含但有重叠部分时，选择一个点在b_i更小的区间的最末端，则该点一定包含在两个区间内。我们的对不同区间的排序方式（即贪心准则）是按b_i从小到大i排序所有的区间，当b_i相同时则按照a_i从大到小进行排序。这样排序以后即使有包含的区间，小区间也一定会排在前面。接下来取第一个区间的最后一个点，然后向后查找第一个不包含该点的区间，取该区间的最后一个点，以此类推直到结束。
总结：
“首先考虑区间包含的情况，当小区间被满足时大区间一定被满足。所以我们应当优先选取小区间中的点，从而使大区间不用考虑。按照上面的方式排序后，如果出现区间包含的情况，小区间一定在大区间里。所以此情况下我们会优先选择小区间。”
【参考代码】
#include<bits/stdc++.h> using namespace std; const int maxn=10010; struct Node{ int begin; //开始的点 int end; //结束的点 }node[maxn]; bool cmp(Node a,Node b) { return a.end<b.end; //由小到大排序 } int main() { int n,ans; while(scanf("%d",&n)) { for(int i=0;i<n;++i)//输入区间 并处理 { scanf("%d %d",&node[i].begin,&node[i].end); } sort(node,node+n,cmp);//将区间按右端点排序,右端点小的在前面 ans=0; int position=-1;//pos代表第一个区间选取的点 for(int i=0;i<n;++i) { if(node[i].begin>position) { position=node[i].end; ++ans; } } printf("%d\n",ans); } }其次，用队列的方式也可以做
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool cmp (pair<int, int> &a,pair<int, int> &b){ return a.second<b.second ? true:a.second==b.second&&a.first>b.first; } int main(int argc, const char * argv[]) { int n;cin>>n; vector<pair<int, int> > v; int x,y; while (n--) { cin>>x>>y; v.push_back(pair<int, int>(x,y)); } sort(v.begin(), v.end(), cmp); int cur_point=v.front().second; int num=1; for (int i=1; i<v.size(); i++) { if(v[i].first>cur_point) { cur_point=v[i].second; num++; } } cout<<num<<endl; return 0; }【例题——>另一种思路】
【题目描述】
某条街道上有很多个广告位，一个公司在这条街上投放广告，因为不同地方的人流量是不同的，所以公司先做了个调查，共调查了N个人，知道了他们每个人每天在街上走的路段。现在要求找到一些广告位，使得广告位数量最少，但是要求调查到的那些每人至少看到广告K次。如果有人走的路段广告位少于K个，那么要求他在这个路段的所有广告位都要看到。输出要求的广告位的位置。
区间的右端点即可。择区间的右端点即可。
分析： 典型的区间选点问题。
1.先按照区间右端点从小到大的顺序排列，右端点相等，按左端点从大到小的顺序。
2.循环遍历每个区间，把访问过的位置i即放了广告牌的位置用vis【i】设为1
①若区间长度<=K,则区间内的每个位置全部要放广告牌，从区间左端点->右端点挨个遍历，未访问（vis【i】==0）的放置广告牌，计数器cnt++
②若区间长度>K，则区间内只要放置K个广告牌即可，先从左端点->右端点挨个遍历，计算已经放置的广告牌数num,得到的num>=K，则不用再放，继续下一个区间，小于K，则偏向右方的位置优先放置广告牌，即从右端点-->左端点遍历，未访问的放广告牌
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #define de 10000 using namespace std; int K,n; //K表示最少看到的广告牌数，n为人的个数 struct Node { int left,right; bool operator<(Node p) //自定义比较函数 { if(right!=p.right) //按照区间右端点从小到大的顺序排序，相等按左端点从大到小的顺序排序 return right<p.right; else return left>p.left; } }; Node p[1005]; int vis[20005]; void solve() { int i,j,cnt=0,num; for(i=0;i<n;i++) { if((p[i].right-p[i].left+1<=K)) //如果区间长度小于K，则区间内所有数都要放广告牌 { for(j=p[i].left;j<=p[i].right;j++) //从区间左端点遍历到右端点，未访问过的+1，设为访问过 { if(vis[j]==0) { vis[j]=1; cnt++; } } } else //区间长度大于K { num=0; for(j=p[i].left;j<=p[i].right;j++) //先从区间左端点到右端点，计算已经放的广告牌数num { if(vis[j]==1) num++; } if(num<K) //num不够规定的K个 for(j=p[i].right;j>=p[i].left;j--) //从区间右端点到左端点，没访问的放广告牌，当num==k时跳出 { if(vis[j]==0) { num++; cnt++; vis[j]=1; } if(num>=K) break; } } } cout<<cnt<<endl; for(i=0;i<20005;i++) if(vis[i]==1) cout<<i-10000<<endl; //注意输出的是i-10000 } int main() { int i,j,m,left,right; cin>>m; for(i=0;i<m;i++) { cin>>K>>n; for(j=0;j<n;j++) { cin>>left>>right; if(left>right) { left=left+right; right=left-right; left=left-right; } p[j].left=left+de; //+10000保证区间内的数都是整数，vis便于访问 p[j].right=right+de; } sort(p,p+n); solve(); memset(vis,0,sizeof(vis)); if(i!=m-1) cout<<endl; } return 0; }(adsbygoogle = window.adsbygoogle || []).push({});