【贪心】线段不重合最大值（界点位置移动）

题目描述

数轴上有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，可后面还有比这个末位置小的。

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

• 简单代码，大神勿喷。