D - Meeting Room Reservation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、会社の会議室の予約管理を担当しています。この会社には会議室が 1 つしかなく、同時に行える会議は最大 1 つだけです。

ある日、 N 件の会議の予約申請が届きました。 i 番目の会議は時刻 L_i に開始し、時刻 R_i に終了します（ L_i < R_i ）。会議室は 1 つしかないため、時間帯が重なる会議を同時に行うことはできません。

ここで、2 つの会議 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
  • 1 行目には、会議の予約申請の件数を表す N が与えられる。
  • 2 行目から N + 1 行目では、各会議の開始時刻 L_i と終了時刻 R_i がスペース区切りで与えられる。
  • 1 + i 行目では、 i 番目の会議の開始時刻 L_i と終了時刻 R_i が与えられる。

出力

互いに重ならないように選べる会議の最大数を 1 行で出力せよ。

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

Score : 400 pts

Problem Statement

Takahashi is in charge of managing meeting room reservations at his company. The company has only 1 meeting room, and at most 1 meeting can be held at any given time.

One day, N meeting reservation requests arrived. The i-th meeting starts at time L_i and ends at time R_i (L_i < R_i). Since there is only one meeting room, meetings with overlapping time slots cannot be held simultaneously.

Here, two meetings i and j are said to "overlap" if the intervals (L_i, R_i) and (L_j, R_j) have a common part, that is, if L_i < R_j and L_j < R_i both hold. If the end time of one meeting coincides with the start time of another meeting (for example, R_i = L_j), they are considered non-overlapping and can be held consecutively.

Takahashi wants to schedule as many meetings as possible. Find the maximum number of meetings that can be selected such that no two of them overlap.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq L_i < R_i \leq 10^9
  • All input values are integers.

Input

N
L_1 R_1
L_2 R_2
:
L_N R_N
  • The first line contains N, the number of meeting reservation requests.
  • From the 2nd line to the (N + 1)-th line, the start time L_i and end time R_i of each meeting are given separated by a space.
  • The (1 + i)-th line contains the start time L_i and end time R_i of the i-th meeting.

Output

Print the maximum number of meetings that can be selected such that no two of them overlap, in a single line.

Sample Input 1

5
1 5
3 8
1 3
5 8
2 6

Sample Output 1

2

Sample Input 2

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

Sample Output 2

5

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

Sample Output 3

6