Pythonで最長の好調区間（Well-Performing Interval）を求めるアルゴリズム

問題概要

ある従業員の1日ごとの勤務時間を記録したリスト hours が与えられます。ここで、勤務時間が8時間より厳密に大きい日を「疲労日（tiring day）」と定義します。また、「好調な区間（well-performing interval）」とは、区間内に含まれる疲労日の数が、疲労日以外の日数よりも厳密に多い連続した日数の区間を指します。

このとき、最も長い好調な区間の長さを求めるのが本記事の課題です。たとえば、入力が [9,9,6,0,6,6,9] の場合、出力は 3 となります。これは、最も長い好調な区間が [9,9,6] であるためです。

解法のアプローチ

この問題は、累積スコア（プレフィックスサムの考え方）とハッシュマップを組み合わせることで、O(n) の計算量で効率的に解くことができます。手順は以下の通りです。

• temp := 0、ans := 0、マップ d、corner := 0 を初期化します。
• i を 0 から hours 配列のサイズ − 1 まで繰り返します。
  • hours[i] > 8 であれば temp に 1 を加算し、そうでなければ 1 を減算します。
  • hours[i] > 8 の場合、corner = 1 とします。
  • temp > 0 の場合、ans := max(ans, i + 1) とします（先頭から現在位置まで全体が好調な区間になるため）。
  • temp がまだマップ d に存在しない場合、d[temp] := i を登録します（同じ値なら最も早いインデックスを保持）。
  • temp − 1 がマップ d に存在する場合、ans := max(ans, i − d[temp − 1]) とします（その位置の次から現在位置までの区間の合計が正になるため）。

ポイントは、temp を「疲労日を +1、それ以外を −1」として累積した値とみなし、区間の合計が正（疲労日が過半数）になるところを探すことです。各値が最初に出現したインデックスだけを記録しておくことで、最長の区間を効率よく特定できます。

実装例

以下に Python での実装を示します。

class Solution(object):
   def longestWPI(self, hours):
      temp = 0
      ans = 0
      d = {}
      corner = 0
      for i in range(len(hours)):
         temp += 1 if hours[i]>8 else -1
         if hours[i]>8:
            corner = 1
         if temp>0:
            ans = max(ans,i+1)
         if temp not in d:
            d[temp]=i
         if temp-1 in d:
            ans = max(ans,i-d[temp-1])
      return max(ans,0)
ob = Solution()
print(ob.longestWPI([9,9,6,0,6,6,9]))

入力

[9,9,6,0,6,6,9]

出力

3

まとめ

このアルゴリズムでは、配列を一度走査するだけで答えが求まるため、時間計算量は O(n)、ハッシュマップの分の空間計算量は O(n) となります。累積和とハッシュマップを組み合わせるテクニックは、「部分配列の合計が条件を満たす最長の区間を求めよ」という種類の問題全般に応用できるので、ぜひ覚えておきましょう。