Let \(C_i\) denote the number of turrets guarding wall \(i\) \((1 \leq i \leq N)\).

The answer to the problem is the minimum value in \(C\). Let \(m\) be this minimum value. If less than \(m\) turrets are destroyed, every wall \(i\) will be guarded by at least \((C_i-m+1)\) turrets, which is positive; so any wall is guarded by at least one turret. Conversely, for a wall \(j\) with \(C_j=m\), if we destroy all the \(m\) turrets that guard wall \(j\), the wall \(j\) will be guarded by zero turrets, so there will exist a wall that is not guarded by any turret. Hence, the minimum value in \(C\) is the answer.

Let us describe how to compute \(C\) from the input. \(C_i\) equals the number of \(j\) (\(1 \leq j \leq M\)) such that \(L_j \leq i \leq R_j\). Equivalently, starting with \(C=(0,0,\ldots,0)\), for each \(i\) (\(1 \leq i \leq M\)), we increment \(C_{L_i},C_{L_i+1},\ldots,C_{R_i}\) by 1 to obtain the desired \(C\). Performing this naively would result in a time complexity of \(O(NM)\), which exceeds the time limit for this problem’s constraints.

This computation can be significantly speeded up using a cumulative sum trick (called Imos method by Japanese community). We can compute \(C\) by the following procedure. For convenience, assume \(C\) has length \(N+1\).

• Initialize \(C=(0,0,\ldots,0)\)
• For \(i=1,2,\ldots,M\) in order:
  • \(C_{L_i} \leftarrow C_{L_i}+1\)
  • \(C_{R_i+1} \leftarrow C_{R_i}-1\)
• For \(i=2,\ldots,N+1\) in order:
  • \(C_{i} \leftarrow C_{i}+C_{i-1}\)

The minimum value among \(C_1,C_2,\ldots,C_N\) is the solution (\(C_{N+1}\) will always be 0).

Thus, this problem can be solved with a time complexity of \(\mathrm{O}(N+M)\).

Sample code (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;
}

Sample code (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)