この問題は俗にimos法と呼ばれる、累積和の逆操作を用いることで高速に求めることができます。

累積和は数列同士の和を保ちます。つまり、「数列 \(A\) の累積和と数列 \(B\) の累積和を足した数列」は「数列 \(A\) と数列 \(B\) を足した数列の累積和」になります。

                  差分 ←      → 累積和
A   0  1  0  0  1  0  0        0  0  1  1  1  2  2  2 
B   0  0 -1  0  0  2  0        0  0  0 -1 -1 -1  1  1
A+B 0  1 -1  0  1  2  0        0  0  1  0  0  1  3  3

また「ある区間の要素が \(1\) でそれ以外は全て \(0\)」という数列に対し、累積和の逆操作を行うと「\(1\) と \(-1\) が \(1\) 個ずつで他は全て \(0\) 」という数列になります。

    0   1   0   0   0  -1   0   0
            累積和↓   ↑差分
  0   0   1   1   1   1   0   0   0

よって「 \((0,\dots,0,1,\dots,1,0,\dots,0)\) の形の数列 \(M\) 個の和」は「\((0,\dots,0,1,0,\dots,0,-1,0,\dots,0)\) の形の数列 \(M\) 個の和の累積和」となり、これは \(O(N+M)\) で求めることができます。

このように、累積和の逆操作を用いて計算を高速化する手法全般をimos法と呼びます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  vector<int>a(n+1);
  for(int i=0; i<m; i++){
    int l, r;
    cin >> l >> r;
    a[l-1]++;
    a[r]--;
  }
  for(int i=0; i<n; i++){
    a[i+1] += a[i];
  }

  int ans = 0;
  for(int i=0; i<n; i++){
    if(a[i] >= k){
      ans++;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N, M, K = map(int, input().split())
A = [0] * (N+1)
for _ in range(M):
  L, R = map(int, input().split())
  A[L-1] += 1
  A[R] -= 1

for i in range(N):
  A[i+1] += A[i]

ans = 0
for a in A:
  if a >= K:
    ans += 1
print(ans)