筆記：【演算法新手村】[初階]筆記06 - 差分(一維)

題目翻譯

有n 個航班，編號從 1 到 n。給定一個預訂紀錄陣列 bookings，其中 bookings[i] = [firstᵢ, lastᵢ, seatsᵢ]，代表從航班 firstᵢ 到 lastᵢ（包含這兩個航班）的範圍內，每一個航班都預訂了 seatsᵢ 個座位。
請回傳一個長度為 n 的陣列 answer，其中 answer[i] 是第 i 個航班被預訂的總座位數。

限制:

• 1 <= n <= 2 * 10⁴
• 1 <= bookings.length <= 2 * 10⁴
• bookings[i].length == 3
• 1 <= firstᵢ <= lastᵢ <= n
• 1 <= seatsᵢ <= 10⁴

這題其實就是很明顯要你使用差分，基本上跟筆記中相同，不過多贅述，這邊提一點：如果你不習慣對索引0進行特判，你可以在建立差分陣列時讓索引從1開始，其他沒什麼要提的。

這邊提一下暴力解，暴力解下中途的值有可能會超出int的範圍，要改用unsigned int/long long，並且效率感人(1541ms，用差分是0ms)，註：數值僅供參考，並不是評判的唯一標準

程式碼實作 (C++)

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n);

        int row = bookings.size();

        for(int i = 0 ; i < row ; i++){
            
            int l = bookings[i][0]-1;
            int r = bookings[i][1]-1;
            int k = bookings[i][2];

            res[l] += k;
            if(r + 1 < n)
                res[r+1] -= k;
        }

        vector<int> ans(n);

        for(int i = 0 ; i < n ;i++){
            if(i == 0){
                ans[i] = res[i];
                continue;
            }
            ans[i] = ans[i-1] + res[i];
        }

        return ans;
    }
};