D - Meeting Room Reservation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はオフィスの会議室管理を担当しています。今日は N 件の会議が予定されており、すべての会議をいずれかの会議室に割り当てる必要があります。

N 件の会議には番号 1 から N が付けられています。会議 i（1 \leq i \leq N）は時刻 S_i に開始し、時刻 E_i に終了します。各会議は半開区間 [S_i, E_i) の間、会議室を占有します。

2 つの会議 i, j が同じ会議室に割り当てられるためには、区間 [S_i, E_i) と [S_j, E_j) が共通部分を持たないことが必要です。特に、ある会議の終了時刻と別の会議の開始時刻が一致する場合、それらは同じ会議室で連続して行うことができます。

オフィスには十分な数の会議室が利用可能ですが、高橋君はできるだけ少ない会議室で全 N 件の会議をまかないたいと考えています。

各会議をちょうど 1 つの会議室に割り当て、どの会議室においても時間区間が重なる会議が存在しないようにするとき、使用する会議室の数の最小値を求めてください。

制約

  • 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
  • 1 行目には、会議の件数を表す整数 N が与えられる。
  • 2 行目から N + 1 行目では、各会議の開始時刻と終了時刻が与えられる。1 + i 行目（1 \leq i \leq N）には、会議 i の開始時刻 S_i と終了時刻 E_i がスペース区切りで与えられる。

出力

全 N 件の会議を割り当てるために必要な会議室の最小数を 1 行で出力せよ。

入力例 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

Score : 400 pts

Problem Statement

Takahashi is in charge of managing the meeting rooms at his office. Today, N meetings are scheduled, and all meetings must be assigned to some meeting room.

The N meetings are numbered from 1 to N. Meeting i (1 \leq i \leq N) starts at time S_i and ends at time E_i. Each meeting occupies a meeting room during the half-open interval [S_i, E_i).

For two meetings i, j to be assigned to the same meeting room, the intervals [S_i, E_i) and [S_j, E_j) must not overlap. In particular, if the end time of one meeting coincides with the start time of another meeting, they can be held consecutively in the same meeting room.

The office has a sufficient number of meeting rooms available, but Takahashi wants to accommodate all N meetings using as few meeting rooms as possible.

Assign each meeting to exactly one meeting room such that no meeting room contains meetings with overlapping time intervals. Find the minimum number of meeting rooms required.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq S_i < E_i \leq 10^9
  • All input values are integers.
  • There may be multiple meetings with the same pair of start time and end time.

Input

N
S_1 E_1
S_2 E_2
\vdots
S_N E_N
  • The first line contains an integer N, representing the number of meetings.
  • From the 2nd line to the (N + 1)-th line, the start time and end time of each meeting are given. The (1 + i)-th line (1 \leq i \leq N) contains the start time S_i and end time E_i of meeting i, separated by a space.

Output

Print in one line the minimum number of meeting rooms required to assign all N meetings.

Sample Input 1

3
1 4
2 6
4 7

Sample Output 1

2

Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

4

Sample Input 3

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

Sample Output 3

4

Sample Input 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

Sample Output 4

5

Sample Input 5

1
0 1000000000

Sample Output 5

1