ヒント → https://atcoder.jp/contests/arc190/editorial/11715

\(S=\lbrace 1,2,\ldots,N\rbrace\)，\(I_i=\lbrace L_i,\ldots,R_i\rbrace\)と書くことにします．

[1] コスト \(2\) 以下で目標達成できる場合

まず次は明らかです：

• コスト \(0\) で目標を達成することは出来ない．
• コスト \(1\) で目標が達成できるのは，\(I_i=S\) を満たす \(i\) が存在する場合のみである．

コスト \(2\) で目標を達成する方法を考えます．使う操作の種類で分類すれば，次の \(3\) 通りの場合を考えればよいです．

• \(I_i\cup I_j=S\) となる \(i,j\) が存在する場合．
• \(I_i\cup (S\setminus I_j)=S\) となる \(i,j\) が存在する場合
• \((S\setminus I_i)\cup (S\setminus I_j)=S\) となる \(i,j\) が存在する場合

最初の場合は，\(1\in I_i\), \(N\in I_j\) として調べればよく，最も長い \(I_i, I_j\) を貪欲に選ぶことで判定できます．

\(2\) 番目の場合は，\(I_i\subset I_j\) と言い換えられます．包含関係にある区間の存在を確かめればよく，これは区間を \(L_i\) や \(R_i\) でソートすれば調べることができます．

\(3\) 番目の場合は，\(I_i\cap I_j=\emptyset\) と言い換えられます．\(I_i\) が左側にある場合を調べればよく，条件は \(R_i<L_j\) と言い換えられるため，\(\min(R), \max(L)\) を調べればよいです．

これでコスト \(2\) 以下で目標を達成できるか否かが判定できました．

[2] コスト \(2\) 以下で目標達成できない場合

この場合特に，区間同士に包含関係がありません．このような区間は適切に添字をつけなおせば，\(L_1<L_2<\cdots\) かつ \(R_1<R_2<\cdots\) が成り立つようにできます．さらにどの \(2\) つの区間も交わることから，

\(L_1<L_2<\cdots<L_M\leq R_1<R_2<\cdots <R_M\)

となっていることが分かります．このことから次が分かります：\( M\geq 3\) ならば，コスト \(3\) 以下で目標を達成することができる．

実際上のように添字を付けかえたうえで，\(I_1, I_3\) には操作 \(1\) を，\(I_2\) には操作 \(2\) を行えばよいです．

解答例：https://atcoder.jp/contests/arc190/submissions/61252862