Pythonで解く企業のフライト予約問題｜差分配列と累積和による効率的な座席集計

n便のフライトがあり、それぞれ1からnまでのラベルが付けられています。ここにフライト予約のリストが与えられ、i番目の予約 bookings[i] = [i, j, k] は「i番からj番までのフライト（両端を含む）でk席を予約した」ことを表します。このとき、各フライトの予約座席数をラベル順に並べた長さnの配列 answer を求めます。

例えば、入力が [[1,2,10],[2,3,20],[2,5,25]]、n = 5 の場合、出力は [10, 55, 45, 25, 25] となります。

解法のアプローチ：差分配列の活用

この問題は、各予約のたびに区間内の全要素へ直接加算すると計算コストが大きくなります。そこで「差分配列」と呼ばれるテクニックを使うと効率的に解けます。区間の始点で値を加算し、終点の次の位置で減算しておき、最後に累積和を取ることで、すべてのフライトの合計座席数を一括して求められます。

具体的な手順は以下の通りです。

• サイズnの配列 res を作成し、すべて0で初期化する
• bookings の各エントリ i について以下を処理する
  • res[i[0] - 1] += i[2]（区間の始点で座席数を加算）
  • i[1] < n の場合、res[i[1]] -= i[2]（区間の終点の次の位置で減算）
• i を 1 から n - 1 まで順に処理する
  • res[i] += res[i - 1]（累積和を計算）
• res を返す

それでは、実際の実装を見て理解を深めましょう。

実装例

class Solution(object):
    def corpFlightBookings(self, bookings, n):
        res = [0 for i in range(n)]
        for i in bookings:
            res[i[0]-1]+=i[2]
            if(i[1]<n):
                res[i[1]]-=i[2]
        for i in range(1,n):
            res[i]+=res[i-1]
        return res
ob = Solution()
print(ob.corpFlightBookings([[1,2,10],[2,3,20],[2,5,25]],5))

入力

[[1,2,10],[2,3,20],[2,5,25]]
5

出力

[10, 55, 45, 25, 25]

計算量のポイント

この手法を用いると、時間計算量は O(n + m)（mは予約の件数）、空間計算量は O(n) に抑えられます。各予約ごとに区間全体を更新する素朴な実装（O(n × m)）と比べて大幅な高速化が可能です。区間への加算・減算処理が多数発生する問題では、差分配列＋累積和の組み合わせが非常に有効なので、ぜひ覚えておきましょう。