\(C_i\) を 城壁 \(i\) を守っている砲台の数 \((1 \leq i \leq N)\)とします。

このとき、\(C\) の最小値が答えとなります。\(C\) の最小値を \(m\) としたとき、\(m\) 個未満の砲台を破壊してもどの城壁 \(i\) も \(C_i-m+1\) 個以上の砲台が守っています。これは必ず正なのでどの城壁も \(1\) 個以上の砲台に守られています。 逆に、\(C_j=m\) となる \(j\) について城壁 \(j\) を守っている \(m\) 個の砲台を全て破壊すると、城壁 \(j\) を守っている砲台は \(0\) 個になり、どの砲台にも守られてない城壁が存在する状態になります。よって、\(C\) の最小値が答えとなります。

入力から \(C\) を計算する方法について考えます。 \(C_i\) は\(L_j \leq i \leq R_j\) を満たす \(j(1 \leq j \leq M)\) の個数と等しいです。これを言い換えると、初め \(C=(0,0,\ldots,0)\) とし、各 \(i(1 \leq i \leq M)\) について \(C_{L_i},C_{L_i+1},\ldots,C_{R_i}\) に \(1\) を加算したものが求めるべき \(C\) です。このまま愚直に計算すると時間計算量が \(O(NM)\) となり、この問題の制約下では実行時間制限に間に合いません。

この処理は imos法 を用いることで高速化できます。以下のような手順で \(C\) を計算することが可能です。また、便宜上 \(C\) は長さ \(N+1\) であるとします。

• \(C=(0,0,\ldots,0)\) と初期化する
• \(i=1,2,\ldots,M\) の順で以下を行う
  • \(C_{L_i} \leftarrow C_{L_i}+1\)
  • \(C_{R_i+1} \leftarrow C_{R_i}-1\)
• \(i=2,\ldots,N+1\) の順で以下を行う
  • \(C_{i} \leftarrow C_{i}+C_{i-1}\)

\(C_1,C_2,\ldots,C_N\) の最小値が答えです(\(C_{N+1}\) は常に \(0\) になります)。

よって時間計算量 \(\mathrm{O}(N+M)\) でこの問題を解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> imos(n + 1);
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        l--;
        imos[l]++, imos[r]--;
    }
    for (int i = 1; i <= n; ++i)
        imos[i] += imos[i - 1];
    int ans = 1e9;
    for (int i = 0; i < n; ++i)
        ans = min(ans, imos[i]);
    cout << ans << endl;
}

実装例(Python)

n, m = map(int, input().split())
imos = [0] * (n + 1)
for _ in range(m):
    l, r = map(int, input().split())
    l -= 1
    imos[l] += 1
    imos[r] -= 1
for i in range(1, n + 1):
    imos[i] += imos[i - 1]
ans = 1e9
for i in range(n):
    ans = min(ans, imos[i])
print(ans)