[Leetcode] Medium : Corporate Flight Bookings

Description

There are n flights that are labeled from 1 to n.

You are given an array of flight bookings bookings, where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi seats reserved for each flight in the range.

Return an array answer of length n, where answer[i] is the total number of seats reserved for flight i.

 

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
Flight labels:        1   2   3   4   5
Booking 1 reserved:  10  10
Booking 2 reserved:      20  20
Booking 3 reserved:      25  25  25  25
Total seats:         10  55  45  25  25
Hence, answer = [10,55,45,25,25]

Example 2:

Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]
Explanation:
Flight labels:        1   2
Booking 1 reserved:  10  10
Booking 2 reserved:      15
Total seats:         10  25
Hence, answer = [10,25]

 

My Solution

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        total_seats = [0] * (n + 1)
        
        for i, j, seat in bookings:
            total_seats[i-1] += seat
            total_seats[j] -= seat
        
        for k in range(1, n):
            total_seats[k] += total_seats[k-1]
        
        return total_seats[: n]

처음에는 중첩 for문을 이용하여 풀려고 했으나 timelimitation이 떠서 O(N)으로 풀어야 겠다고 생각했습니다. 도저히 방법을 몰라 다른 풀이들을 살펴봤을때, Prefix Sum 알고리즘인 위의 방법을 이용하여 풀었더라고요. 처음에는 이해하기 어려웠는데 직접 손으로 풀어보니 이해가 됐습니다! 이런 방법은 다들 어떻게 생각해내는지.... 새삼 코딩테스트 머리는 따로 있나봐요....