算法基础-贪心

3
-1 1
2 4
3 5

2

sort(nodes, nodes + n);
   	int res = 0, ed = -2e9;
   	for(int i = 0; i < n; i ++)
   		if(nodes[i].l > ed)
   		{
   			res ++ ;
   			ed = nodes[i].r;
   		}

/**********************************************
*             她的店里只卖樱花                  *
***********************************************/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map> 
#include <queue>
using namespace std;
#define fi first
#define se second
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define ios_op cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define endl '\n'
#define sendl " \n"
typedef priority_queue<int, vector<int>, greater<int> > PQ;
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const int Inf = 0x3f3f3f3f, Null = 0x80808080;
const double eps=1e-6;
const double PI=acos(-1.0);
const int MOD = 1e9 + 7;
const int N = 100010;
int n;

struct Node{
	int l, r;
	bool operator< (const Node& w)const{
		return r < w.r;
	}
}nodes[N];

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
  while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

template <typename T> void print(T x) {
    if (x < 0) { putchar('-'); print(x); return ; }
    if (x >= 10) print(x / 10);
    putchar((x % 10) + '0');
}

int main (){
   	cin >> n;
   	for(int i = 0; i < n; i ++)
   	{
   		int l, r; 
   		cin >> l >> r;
   		nodes[i] = {l, r};
   	}
   	sort(nodes, nodes + n);
   	int res = 0, ed = -2e9;
   	for(int i = 0; i < n; i ++)
   		if(nodes[i].l > ed)
   		{
   			res ++ ;
   			ed = nodes[i].r;
   		}
   	cout << res << endl;
    return 0;
}