摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
线段覆盖 ★☆☆☆☆ 答案正确 100 2014-10-11 12:53:32

题意

在数轴上,有若干区间,要求去掉若干区间后,使得没有一个点同时属于两个以上区间内部(端点可以重叠),如图。

1214_01.png

 

题解

采取贪心的策略。

什么样的区间被选择风险最小,当然是结束点最小的区间:

1214_02.png

 

于是按照这个策略,就优先选择能够放下去的结束点最小的区间,于是排序+判断一下就可以了。

代码

1214.cpp代码已折叠
展开折叠内容
#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;
}

著作权声明[编辑]

关于[编辑]