机房活动安排

题目描述

机房一天内有 $n$ 个候选活动。第 $i$ 个活动占用时间区间为 $[s_i,e_i)$，即在 $s_i$ 时刻开始、$e_i$ 时刻结束。一个机房同一时刻只能进行一个活动。请安排尽可能多的活动，求最多能安排多少个。

输入格式

第一行输入整数 $n$。接下来 $n$ 行，每行两个整数 $s_i,e_i$。

输出格式

输出最多可以安排的活动数量。

样例

7
1 3
2 4
3 5
0 7
5 7
5 9
8 9

4

说明

区间采用左闭右开表示，因此一个活动在 3 时刻结束，另一个活动可以在 3 时刻开始。核心策略是优先选择结束时间更早的活动，为后续留下更多空间。

数据范围

$1\le n\le 2\times10^5$，$0\le s_i<e_i\le 10^9$。