NC24867 Selfish Grazing 经典贪心

题意: 给定多条线段[L,R],求最多多少条线段不相交

• 按结束点R排序,挨个挑选即可

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "\033[39;0m" << endl; }
#endif

template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

int n, m, Q, K;

struct Node {
	int lef, rig;
	bool operator < (const Node& no) const {
		return rig==no.rig ? lef<no.lef : rig<no.rig;
	}
} a[MAXN];

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	scanf("%d ", &n);
	for(int i=1; i<=n; i++)
		scanf("%d %d ", &a[i].lef, &a[i].rig);
	sort(a+1, a+1+n);
	int ans = 0, lst = -1;
	for(int i=1; i<=n; i++) {
		if(a[i].lef >= lst) {
			lst = a[i].rig;
			ans ++;
		}
	}
	printf("%d\n", ans);


#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}