prefix_sum.py

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        prefix_sum = [0] * (n + 1)
        
        # 1. Build prefix sum array
        
        # for booking [1, 3, 5] and n = 5 prefix sum array:
        # [0, 0, 0, 0, 0] -> [5, 0, 0, -5, 0, 0]
        for lo, hi, seats in bookings:
            prefix_sum[lo - 1] += seats
            prefix_sum[hi] -= seats
            
        # 2. Build result array from prefix sum array
        
        # [5, 0, 0, -5, 0, 0] -> [5, 5, 5, 0, 0]
            
        ret = [0] * n
        ret[0] = prefix_sum[0]
        
        for i in range(1, n):
            ret[i] = ret[i - 1] + prefix_sum[i]
            
        return ret