51Nod 不重叠的线段（贪心）

X轴上有N条线段，每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。（注：起点或终点重叠，不算重叠）。

例如：[1 5][2 3][3 6]，可以选[2 3][3 6]，这2条线段互不重叠。

Input

第1行：1个数N，线段的数量(2 <= N <= 10000)

第2 - N + 1行：每行2个数，线段的起点和终点(-10^9 <= S,E <= 10^9)

Output

输出最多可以选择的线段数量。

Input示例

3

1 5

2 3

3 6

Output示例

2
将线段排过序之后，数目最多就是每个线段的终点坐标尽可能靠左，因此贪心解决

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <stack>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <cassert>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#pragma comment(linker, "/stck:1024000000,1024000000")

#define lowbit(x) (x&(-x))

#define max(x,y) (x>=y?x:y)

#define min(x,y) (x<=y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.1415926535897932384626433832

#define ios() ios::sync_with_stdio(true)

#define INF 0x3f3f3f3f

#define mem(a) ((a,0,sizeof(a)))

struct node

{

    int u,v;

    bool operator<(const node a)

    {

        return a.u==u?a.v>v:a.u>u;

    }

}e[];

int n;

int main()

{

    scanf("%d",&n);

    for(int i=;i<n;i++)

        scanf("%d%d",&e[i].u,&e[i].v);

    sort(e,e+n);

    int ans=,mark=e[].v;

    for(int i=;i<n;i++)

    {

        if(e[i].u>=mark){ans++,mark=e[i].v;}

        else if(e[i].u<mark && e[i].v<mark) mark=e[i].v;

    }

    printf("%d\n",ans);

    return ;

}