残す弦の本数最小化問題を解きます。適切な処理によって、 \(L_i,R_i \in [1,2N]\) かつ周波数の和集合は区間 \([S,T]\) になるとして良いです。

ここで \([S,T]\) 内の整数を頂点とし、\(i+1→i\) にコスト \(0\) 、\(L_i→R_i\) にコスト \(1\) の辺を張ったグラフを考えると、\(S-T\) 最短路のコストが弦の本数の最小値と一致することが分かります。よって、01BFSによって線形時間で解くことができます(座標圧縮を含めた計算量は \(O(N \log N)\) です)。