F - Not All Covered Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder 王国には 1 から N まで番号がつけられた N 個の城壁があります。また、 M 個の砲台があります。

砲台 i は L_i 以上 R_i 以下の番号の城壁を守っています。

ある砲台を破壊すると、その砲台が守っていた城壁はその砲台により守られなくなります。

どの砲台にも守られていない城壁が存在する状態にするためには、最小で何個の砲台を破壊する必要がありますか？

制約

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
L_1 R_1
L_2 R_2
 \vdots 
L_M R_M

出力

砲台に守られていない城壁が存在する状態にするために破壊する必要がある砲台の個数の最小値を出力せよ。

入力例 1

10 4
1 6
4 5
5 10
7 10

出力例 1

1

砲台 1 を破壊するとどの砲台も城壁 3 を守っていない状態になります。 また、砲台を 1 個も破壊しなければ全ての城壁がどれかの砲台に守られている状態になります。 そのため、1 を出力します。

入力例 2

5 2
1 2
3 4

出力例 2

0

どの砲台も城壁 5 を守っていないため、砲台を 1 個も破壊しないでも砲台に守られていない城壁が存在する状態になります。そのため、0 を出力します。

入力例 3

5 10
2 5
1 5
1 2
2 4
2 2
5 5
2 4
1 2
2 2
2 3

出力例 3

3

Score : 300 points

Problem Statement

In the AtCoder Kingdom, there are N castle walls numbered from 1 through N. There are also M turrets.

Turret i guards castle walls numbered from L_i through R_i.

When a turret is destroyed, the castle walls that were guarded by that turret are no longer guarded by that turret.

What is the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret?

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
L_1 R_1
L_2 R_2
 \vdots 
L_M R_M

Output

Output the minimum number of turrets that need to be destroyed so that at least one castle wall is not guarded by any turret.

Sample Input 1

10 4
1 6
4 5
5 10
7 10

Sample Output 1

1

If turret 1 is destroyed, no turret guards castle wall 3. Also, if no turrets are destroyed, all castle walls are guarded by some turret. Therefore, output 1.

Sample Input 2

5 2
1 2
3 4

Sample Output 2

0

Since no turret guards castle wall 5, there already exists a castle wall not guarded by any turret without destroying any turrets. Therefore, output 0.

Sample Input 3

5 10
2 5
1 5
1 2
2 4
2 2
5 5
2 4
1 2
2 2
2 3

Sample Output 3

3