说明

有 n 个活动，每个活动有开始时间 s_i 和结束时间 f_i（s_i < f_i）。同一时间只能进行一个活动。（一个活动结束时另一个恰好开始不算冲突） 求最多能安排多少个不冲突的活动。

输入格式

第一行，整数 n（1 \le n \le 10^5）。 接下来 n 行，每行两个整数 s_i, f_i（0 \le s_i < f_i \le 10^9）。

输出格式

一行，最多可选活动数。

5
1 4
3 5
0 6
5 7
8 10

3

提示

贪心策略：按**结束时间从小到大**排序，每次选最早结束且不冲突的。 acts.sort(key=lambda x: x[1]) cnt, last = 0, 0 for s, f in acts: if s >= last: cnt += 1 last = f print(cnt) 为什么最优？结束越早，留给后面的时间越多。