线段

https://loj.ac/problem/10007

题目描述

  有(n)条线段，求选出最多线段数使选出线段之间两两没有重合部分。

思路

  把每个线段按照右端点进行升序排序，选择目前能满足之前选择的区间，这个区间一定是满足条件并且右端点最小，如果在它之后又一区间满足必定影响比它大，所以它必定是最优解中的一种方案

代码

#include <bits/stdc++.h>
using namespace std;
struct Segment
{
    int l,r;
}a[1010000];
bool cmp(Segment a,Segment b)
{
    if(a.r!=b.r)return a.r<b.r;
    else return a.l<b.l;
}
int main() 
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+n+1,cmp);
    int s=0,ans=0;
    for(int i=1;i<=n;i++)
        if(a[i].l>=s)
        {
            s=a[i].r;
            ans++;
        }
    printf("%d",ans);
    return 0;
}