C++で本の未読の章の数を数える方法

ペアの配列 P があるとします。P[i] は (l, r) の形式で表され、これに加えて数値 k が与えられます。ここで、n 個の章からなる本を読んでいる状況を考えます。本の各ページは必ずいずれか一つの章にのみ属し、各章は少なくとも1ページ以上を含みます。すでにいくつかのページを読んでおり、ページ番号 k が「まだ読んでいない最初のページ」を示しています。このとき、まだ完全に読み終えていない章の数を求める必要があります。P[i] は各章のページ番号の範囲を表します。

例えば、入力が P = [[1, 3], [4, 7], [8, 11]]; k = 4 の場合、出力は 2 になります。これは、第1章をすでに読み終えており、残りの2章がまだ読まれていないためです。

解決手順

この問題を解くには、以下の手順に従います。

n := P のサイズ
i := 1 で初期化し、i <= n の間、i を1ずつ増やしながら繰り返す:
   k >= P[i - 1, 0] かつ k <= P[i - 1, 1] の場合:
      return n - i + 1
return 0

このアルゴリズムのポイントは、ページ k が属する章を線形探索で見つけることです。k は最初の未読ページであるため、それより前の章はすべて読み終えており、k を含む章から最後の章までは未読のままです。したがって、見つかった章の位置から残りの章数 n - i + 1 を返せば答えが求まります。該当する章が見つからない場合は、すべての章を読み終えているため 0 を返します。

実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> P, int k){
   int n = P.size();
   for (int i = 1; i <= n; i++){
      if (k >= P[i - 1][0] && k <= P[i - 1][1])
         return n - i + 1;
   }
   return 0;
}
int main(){
   vector<vector<int>> P = { { 1, 3 }, { 4, 7 }, { 8, 11 } };
   int k = 4;
   cout << solve(P, k) << endl;
}

入力

{ { 1, 3 }, { 4, 7 }, { 8, 11 } }, 4

出力

2