Pythonでレート制限の条件を満たして処理されるリクエスト数を求めるプログラム

各要素が [uid, time_sec] の形式（uid はユーザーID、time_sec はタイムスタンプ）で構成されるリクエストのリストを考えてみましょう。これは「IDが uid のユーザーが、時刻 time_sec にウェブサイトへリクエストを送信した」ことを意味します。

さらに、2つの値 u と g が与えられます。

• u: 特定の uid に対して、60秒未満の時間枠内で許容される最大リクエスト数
• g: システム全体に対して、60秒未満の時間枠内で許容される最大リクエスト数

リクエストを1件ずつ処理しながらレート制限を適用します。複数のユーザーから同時にリクエストが届いた場合は、uid が小さい方のリクエストが先に処理され、それ以外のリクエストは破棄されます。このとき、正常に処理されるリクエストの総数を求めるのが目的です。

例えば、入力が requests = [[0, 1],[1, 2],[1,3]]、u = 1、g = 5 の場合、出力は 2 になります。ユーザー0とユーザー1はそれぞれ時刻1と2にリクエストを送信できますが、ユーザー1の2つ目のリクエスト（時刻3）は、「1人のユーザーは60秒間に最大1件しか送信できない」という制限に引っかかるため処理されません。

解決のためのアプローチ

この問題は、スライディングウィンドウ（時間窓）を使ったレート制限としてモデル化できます。以下の手順で解きます。

• last := 空のマップ（ユーザーごとのリクエスト時刻を記録）
• total := 空の両端キュー（全体のリクエスト時刻を記録）
• windowtime := 60（時間枠の長さ）
• リクエストを時刻順にソートする。同一時刻の場合は uid の昇順でソートする
• amount := 0（処理成功数のカウンター）
• requests 内の各 r について以下を実行する:
  • [uid, time] := r として分解する
  • total のサイズが0より大きく、かつ total[0] + windowtime <= time の間、total の左端の要素を削除する
  • last[uid] のサイズが0より大きく、かつ last[uid][0] + windowtime <= time の間、last[uid] の左端の要素を削除する
  • total のサイズ < g かつ last[uid] のサイズ < u である場合:
    • last[uid] の末尾に time を追加する
    • total の末尾に time を追加する
    • amount := amount + 1 とする
• amount を返す

ポイントは、古いタイムスタンプを deque の左端から取り除くことで、常に「現在時刻から60秒以内」のリクエストだけを保持している点です。これにより、ユーザー単位とグローバル単位の両方の制限を効率的に判定できます。

実装例

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

from collections import defaultdict, deque
class Solution:
   def solve(self, requests, u, g):
      last = defaultdict(deque)
      total = deque()

      windowtime = 60
      requests.sort(key=lambda x: [x[1], x[0]])

      amount = 0
      for r in requests:
         uid, time = r

         while len(total) > 0 and total[0] + windowtime <= time:
            total.popleft()

         while len(last[uid]) > 0 and last[uid][0] + windowtime <= time:
            last[uid].popleft()

         if len(total) < g and len(last[uid]) < u:
            last[uid].append(time)
            total.append(time)
            amount += 1
      return amount
     
ob = Solution()
requests = [[0, 1],[1, 2],[1,3]]
u = 1
g = 5
print(ob.solve(requests, u, g))

入力

[[0, 1],[1, 2],[1,3]], 1, 5

出力

2