AT_codefestival_2015_final_d 足ゲームII
题目描述
高桥君打算挑战如下的节奏游戏。
- 有 $N$ 个大按钮。每按下一个按钮，必须正好有 $1$ 个人站在上面，不能用其他方式按下。
- 同一个人在同一时刻不能按下 $2$ 个或以上的按钮。
- 如果在时刻 $S_i$ 到 $T_i$ 之间持续按下第 $i$ 个按钮，可以获得 $1$ 分。此时，不要求从头到尾都由同一个人按下，中途可以换人。
- 上下按钮或更换按按钮的人所需的时间可以忽略不计。
高桥君希望和几个人合作，通过这个游戏获得至少 $N-1$ 分。请你求出，为了获得至少 $N-1$ 分，所需的最小人数。
输入格式
输入通过标准输入给出，格式如下：
> $N$
> $S_1$ $T_1$
> $S_2$ $T_2$
> $\vdots$
> $S_N$ $T_N$
- 第 $1$ 行是表示按钮个数的整数 $N$，满足 $2 \leq N \leq 10^5$。
- 接下来的 $N$ 行，每行包含两个整数 $S_i, T_i$，满足 $1 \leq S_i < T_i \leq 10^5$，表示如果在时刻 $S_i$ 到 $T_i$ 之间持续按下第 $i$ 个按钮，可以获得 $1$ 分。
输出格式
输出获得至少 $N-1$ 分所需的最小人数。输出后需换行。
说明/提示
### 样例解释 1
下图表示每个按钮在持续按下时可以获得分数的时间段。除了按钮 $1$ 以外，剩下的按钮可以由 $1$ 个人全部踩完，因此可以获得 $3$ 分。
由 ChatGPT 4.1 翻译