1. 題目

這里有 n 個航班，它們分別從 1 到 n 進行編號。

我們這兒有一份航班預訂表，表中第 i 條預訂記錄 bookings[i] = [i, j, k] 意味著我們在從 i 到 j 的每個航班上預訂了 k 個座位。

請你返回一個長度為 n 的數組 answer，按航班編號順序返回每個航班上預訂的座位數。

示例： 輸入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 輸出：[10,55,45,25,25]提示： 1 <= bookings.length <= 20000 1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000 1 <= bookings[i][2] <= 10000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/corporate-flight-bookings
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 1094. 拼車
LeetCode 370. 區間加法（差分思想）
LeetCode 995. K 連續位的最小翻轉次數（差分思想）
LeetCode 732. 我的日程安排表 III（差分思想）
LeetCode 1674. 使數組互補的最少操作次數（差分思想）
LeetCode 1854. 人口最多的年份（差分）
LeetCode 5767. 檢查是否區域內所有整數都被覆蓋（差分）

• 看數據量這么大，暴力肯定要超時
• 左端點+num，右端點后面-num，中間的狀態不變，就省了給每個位置更新的時間

class Solution { public:vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {vector<int> bk(n+2,0);for(auto& b : bookings){bk[b[0]] += b[2];//左端點+numbk[b[1]+1] -= b[2];//右端點后面 +num}for(int i = 2; i <= n; i++)bk[i] += bk[i-1];return vector<int> (bk.begin()+1, bk.end()-1);} };

344 ms 49.1 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1109. 航班预订统计（差分思想）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。