查看CodeVS/1214的源代码 ←CodeVS/1214

[[分类:贪心]]
==摘要==
{{信息题|线段覆盖|http://www.codevs.cn/problem/1214/|1|100|time=2014-10-11 12:53:32}}
==题意==
在数轴上，有若干区间，要求去掉若干区间后，使得没有一个点同时属于两个以上区间内部（端点可以重叠），如图。
{{大照片| |Knowledge/Algorithm/CodeVS/1214_01.png}}
==题解==
采取贪心的策略。

什么样的区间被选择风险最小，当然是结束点最小的区间：
{{大照片| |Knowledge/Algorithm/CodeVS/1214_02.png}}
于是按照这个策略，就优先选择能够放下去的结束点最小的区间，于是排序+判断一下就可以了。
==代码==
{{折叠|1214.cpp代码已折叠
|<pre>#include<iostream>
#include<algorithm>
#include<climits>
std::pair<int,int> p[101];
int n;
void init()
{
    std::cin>>n;
    for(int i=1;i<=n;++i)
    {
        std::cin>>p[i].first>>p[i].second;
        if(p[i].first<p[i].second)
            std::swap(p[i].first,p[i].second);
    }
    std::sort(p+1,p+n+1);
}
const int process()
{
    int last=INT_MIN,count=0;
    for(int i=1;i<=n;++i)
    {
        if(last<=p[i].second)
        {
            last=p[i].first;
            ++count;
        }
    }
    return count;
}
int main()
{
    init();
    std::cout<<process();
    return 0;
}
</pre>
|code1214}}