← 返回题目列表

AtCoder · math_and_algorithm_bn

082. 间隔调度问题

中文机器翻译题面 查看原题

配点: 1000 点

問題文

今天 N 将放映电影。i 第部电影是时候了 开始于 L_i 和时间 以 R_i 结尾。

我可以从头到尾观看多少部电影?

但是,您可以在看完一部电影后立即开始观看下一部电影,但不能同时观看多于一部电影。 如果您在满足

制約

  • 1 \le N \le 300000
  • 0 \le L_i < R_i \le 86400
  • 所有输入均为整数

部分点

  • N \leq 2000 的情况下回答正确,500 积分。 If you answer all

入力

输入是按以下格式从标准输入给出的。

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

请输出您从头到尾可以观看的电影的最大数量。


入力例 1

3
123 86399
1 86400
86399 86400

出力例 1

2

如果您执行以下操作, 您可以从头到尾观看2 电影。

  • 一、电影 1 到时间 123 到时间 查看最多 86399 。
  • 接下来,电影 3 到时间 86399 到时间 查看最多 86400 。

3 没有办法从头到尾看完所有电影。