← 返回题目列表

AtCoder · awc0036_d

D. 会议室预订

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

分数: 400 分

问题陈述

高桥负责管理他办公室的会议室。今天, N 会议已安排,所有会议必须分配到某个会议室。

的 树的 N 会议编号自 1 to N。会议 i (1 \leq i \leq N) 开始时间 S_i 并于时间结束 E_i。半开期间每次会议占用一个会议室 [S_i, E_i).

两次会议 i, j 被分配到同一个会议室,间隔 [S_i, E_i) 和 [S_j, E_j) 不得重叠。特别是,如果一个会议的结束时间与另一个会议的开始时间一致,则可以在同一会议室连续举行。

办公室有足够数量的会议室,但高桥希望容纳所有会议室 N 会议使用尽可能少的会议室。

将每个会议精确分配到一个会议室,这样就不会出现任何会议室包含时间间隔重叠的会议。找出所需的最少会议室数量。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq S_i < E_i \leq 10^9
  • 所有输入值均为整数。
  • 可能有多个会议具有相同的开始时间和结束时间。

输入

N
S_1 E_1
S_2 E_2
\vdots
S_N E_N
  • 第一行包含一个整数 N,代表会议次数。
  • 从第 2 行到 (N + 1)第行,给出了每次会议的开始时间和结束时间。的 (1 + i)第行(1 \leq i \leq N) 包含开始时间 S_i 和结束时间 会议 E_i 会议的 i,用空格分隔。

输出

在一行中打印分配所有会议室所需的最少会议室数 N 会议。


示例输入 1

3
1 4
2 6
4 7

示例输出 1

2

示例输入 2

4
1 5
2 6
3 7
4 8

示例输出 2

4

示例输入 3

10
0 5
1 3
2 8
3 6
5 10
6 9
7 12
8 11
9 14
1 4

示例输出 3

4

示例输入 4

15
6 14
7 11
8 12
9 13
10 15
0 3
1 4
3 7
14 20
15 18
16 22
20 25
11 16
4 6
18 24

示例输出 4

5

示例输入 5

1
0 1000000000

示例输出 5

1