各弦が出せる周波数を区間 \([L_i,R_i]\) と考えます。

すべての弦が作る区間の和集合を変えずに、残す弦の本数を最小化すればよいです。残す弦が \(M\) 本なら、答えは \(N-M\) 本です。

これは以下のようなアルゴリズムで求めることができます。まず、区間を \(L_i\) の昇順に並べ、連結な区間ごとに次の貪欲法を行います。

1. 現在までに覆えている右端を \(x\) とする
2. \(L_i \le x\) を満たす区間のうち、\(R_i\) が最大のものを残す
3. \(x\) をその区間の右端に更新する

これを連結な区間の右端まで覆うまで繰り返します。

実装例

n = int(input())
lr = [tuple(map(int, input().split())) for _ in range(n)]
lr.sort()

ans = n
i = 0

while i < n:
    # i から始まる連結成分の右端を求める
    j = i
    r = lr[i][1]

    while j + 1 < n and lr[j + 1][0] <= r:
        j += 1
        r = max(r, lr[j][1])

    # 連結成分を最小本数の区間で覆う
    x = lr[i][0]
    p = i

    while True:
        far = x

        while p <= j and lr[p][0] <= x:
            far = max(far, lr[p][1])
            p += 1

        ans -= 1

        if far == r:
            break

        x = far

    i = j + 1

print(ans)