← 返回题目列表

AtCoder · awc0034_d

D. 会议室预订

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

分数: 400 分

问题陈述

Takahashi 负责管理其公司的会议室预订。公司仅有 1 会议室,最多 1 会议可以在任何给定时间举行。

有一天, N 会议预订请求已到达。的 i第 次会议开始时间 L_i 并于时间结束 R_i (L_i < R_i)。由于只有一间会议室,时间重叠的会议无法同时举行。

在这里,两次会议 i 和 j 如果间隔被称为“重叠” (L_i, R_i) 和 (L_j, R_j) 有一个共同的部分,那就是,如果 L_i < R_j 和 L_j < R_i 两者都成立。如果一个会议的结束时间与另一会议的开始时间一致(例如, R_i = L_j),它们被认为是不重叠的并且可以连续持有。

高桥希望安排尽可能多的会议。找到可以选择的最大会议数,使得其中没有两个会议重叠。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq L_i < R_i \leq 10^9
  • 所有输入值均为整数。

输入

N
L_1 R_1
L_2 R_2
:
L_N R_N
  • 第一行包含 N,会议预订请求的数量。
  • 从第 2 行到 (N + 1)第行,开始时间 L_i 和结束时间 每次会议的 R_i 均以空格分隔。
  • 的 (1 + i)-第行包含开始时间 L_i 和结束时间 每次会议的 R_i 的 i第次会议。

输出

在一行中打印可以选择的最大会议数,确保其中没有两个会议重叠。


示例输入 1

5
1 5
3 8
1 3
5 8
2 6

示例输出 1

2

示例输入 2

8
1 4
3 6
2 4
5 9
5 7
7 9
9 10
1 2

示例输出 2

5

示例输入 3

12
0 100
50 150
100 200
200 500
150 300
300 600
500 700
600 800
700 800
750 900
1000 1000000000
999999999 1000000000

示例输出 3

6