【Python】特定の時点で交差している区間の数をカウントする方法

区間のリストと、point という値が与えられているとします。各区間 interval[i] は [si, ei] の形式で表され、区間 i の開始時刻と終了時刻(両端を含む)を意味します。このとき、指定された時点で交差している区間の個数を求める必要があります。

たとえば、入力が intervals = [[2, 6],[4, 10],[5, 9],[11, 14]]、point = 5 の場合、出力は 3 になります。これは、時刻 5 を含む区間が [2, 6]、[4, 10]、[5, 9] の 3 つ存在するためです。

解決アプローチ

この問題は、シンプルな線形探索によって解くことができます。手順は以下の通りです。

• カウンター count を 0 で初期化します。
• intervals 内の各区間から、開始時刻 i と終了時刻 j を取り出します。
• point >= i かつ point <= j を満たす場合、その区間は指定された時点を含んでいるため、count を 1 増やします。
• すべての区間を確認した後、count を返します。

このアルゴリズムの計算量は O(n)(n は区間の数)であり、すべての区間を一度ずつチェックするだけでよいため、非常に効率的です。

実装例

理解を深めるために、以下の Python コードを見てみましょう。

def solve(intervals, point):
   count = 0
   for i, j in intervals:
      if point >= i and point <= j:
         count += 1
   return count

intervals = [[2, 6],[4, 10],[5, 9],[11, 14]]
point = 5
print(solve(intervals, point))

入力

[[2, 6],[4, 10],[5, 9],[11, 14]], 5

出力

3

このように、各区間の開始時刻と終了時刻を比較するだけで、指定した時点に交差する区間の数を簡単に求めることができます。条件判定では「以上」「以下」を使用しているため、区間の端点がちょうど point と一致する場合も正しくカウントされる点に注意してください。