题目描述

数轴上有n条线段，选取其中k条线段使得这k条线段两两没有重合部分，问k最大为多少。

 

输入

第一行为一个正整数n；
在接下来的n行中，每行有2个数ai,bi，描述每条线段。

 

输出

输出一个整数，为k的最大值。

 

样例输入

复制样例数据

3
0 2
2 4
1 3

样例输出

2
  • 贪心性质：不重合最大，先按起始位置排序，如果下一个的开始比上一个终止大即为重合，但要注意界点变化，如果发现不重合的时候，有一个终止位置比现在的终止位置小，终止位置需要发生改变，故代码如下： 
    #include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
struct segment{
    double B;
    double E;
};
segment seg[1100000];
bool cmp(segment a,segment b)
{
    return a.B<b.B;
}
int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&seg[i].B,&seg[i].E);
    sort(seg+1,seg+1+n,cmp);
    m=seg[1].E;
    int cnt=1;
   // printf("\n-------------\n");//确认是否按起始位置排序
    //for(int i=1;i<=n;i++)
    //    printf("%.0lf %.0lf\n",seg[i].B,seg[i].E);
    //printf("--------------\n");
    for(int i=2;i<=n;i++)
    {

        if(seg[i].B-m<0)//如果有重合部分
        {
            if(seg[i].E<m)//保证每一个末位置都最小化
                m=seg[i].E;
            else
                continue;
        }
        else
        {
            cnt++;
            m=seg[i].E;//末位置改变
        }
    }
    printf("%d",cnt);
    return 0;
}

     

PS：如果不加末位置最小化，试一组实例：

4      1   3         3    5        3    4         4     6    答案应该是3，可运行为2，因为第二个实例过了之后，末位置为5，可后面还有比这个末位置小的。

所以应该确保每次指向的数都是满足条件的最小的。

  • 简单代码，大神勿喷。