整数 \(n\) に対し、 \([n,n+1)\) を含む区間の個数を \(f(n)\) とします。すなわち、\(f(n)=\#\{i\mid L_i\le n\lt R_i\}\) です。

区間が互いに交わらないことと、すべての \(n\) で \(f(n)\le 1\) すなわち \(F\coloneqq\sum_{n\in\mathbb{Z}} \max(0,f(n)-1)=0\) であることは同値であるため、これを目指します。

一回の操作で \(F\) の値は高々 \(1\) 減るため、操作前の \(F\) の値を \(F_0\) とすると、答えの下界は \(F_0\) です。

一方、 \(F>0\) の時、 \(f(n)>1\) なる最大の \(n\) をとると、\(R_i=n+1\) なる \(i\) が存在します。\(R_i\) を \(R_i-1\) に置き換えることで、\(f(n)\) の値は \(1\) 減り、\(F\) もまた \(1\) 減少します。よって、これを繰り返すことで操作回数 \(F_0\) は達成可能であるため、結局求める答えは \(F_0\) です。

\(F_0\) の計算方法については、いくつか方法が考えられますが、 \(2\) 種類のみ紹介をすると、

1. 座圧+imos法を用いて \(F_0\) の定義通りに計算する。実装例1(C++)

2. \(L'_1\lt R'_1\lt L'_2\lt R'_2\lt\dots \lt R'_m\) なる \(L'_1, R'_1, L'_2,R'_2,\dots ,R'_m\) で、

\[\bigcup_{i=1}^{n}[L_i,R_i)=\bigcup_{i=1}^{m}[L'_i,R'_i)\]

なるものを取った時、

\[F_0=\sum_{i=1}^{n}(R_i-L_i)-\sum_{i=1}^{m}(R'_i-L'_i)\]

と表せることを利用する。実装例2(C++)

などの方法によって計算が可能です。