【题目描述】

数轴上有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;
}