<p>There are <code>n</code> flights that are labeled from <code>1</code> to <code>n</code>.</p>

<p>You are given an array of flight bookings <code>bookings</code>, where <code>bookings[i] = [first<sub>i</sub>, last<sub>i</sub>, seats<sub>i</sub>]</code> represents a booking for flights <code>first<sub>i</sub></code> through <code>last<sub>i</sub></code> (<strong>inclusive</strong>) with <code>seats<sub>i</sub></code> seats reserved for <strong>each flight</strong> in the range.</p>

<p>Return <em>an array </em><code>answer</code><em> of length </em><code>n</code><em>, where </em><code>answer[i]</code><em> is the total number of seats reserved for flight </em><code>i</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
<strong>Output:</strong> [10,55,45,25,25]
<strong>Explanation:</strong>
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]
</pre>

<p><strong class="example">Example 2:</strong></p>

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

</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= bookings.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>bookings[i].length == 3</code></li>
	<li><code>1 &lt;= first<sub>i</sub> &lt;= last<sub>i</sub> &lt;= n</code></li>
	<li><code>1 &lt;= seats<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& book, int n) {
        // diff array method
        int len = book.size();
        vector<int> ans(n, 0);
        vector<int> diff(n, 0);
        for(auto e: book){
            int fst = e[0]-1;
            int lst = e[1]-1;
            int seats = e[2];

            diff[fst]+=seats;
            if(lst+1<n){
                diff[lst+1]-=seats;
            }
        }

        ans[0] = diff[0];

        for(int i=1; i<n; i++){
            ans[i] = diff[i] + ans[i-1];
        }

        return ans;

        // int len = book.size();

        // vector<vector<int>> fst; // flight, seat
        // vector<vector<int>> lst; // flight, seat
        
        // for(int i=1; i<=len; i++){
        //     fst.push_back({book[i-1][0], book[i-1][2]});
        //     lst.push_back({book[i-1][1], book[i-1][2]});
        // }

        // sort(fst.begin(), fst.end(), [](vector<int> a, vector<int> b){
        //     return a[0]<b[0];
        // });

        // sort(lst.begin(), lst.end(), [](vector<int> a, vector<int> b){
        //     return a[0]<b[0];
        // });
        
        // vector<int> fst_psum(len, 0);
        // vector<int> lst_psum(len, 0);
        // vector<int> fst_idx(len, 0);
        // vector<int> lst_idx(len, 0);

        // fst_psum[0] = fst[0][1];
        // lst_psum[0] = lst[0][1];
        // fst_idx[0] = fst[0][0];
        // lst_idx[0] = lst[0][0];

        // for(int i=1; i<len; i++){
        //     fst_psum[i] = fst_psum[i-1]+fst[i][1];
        //     lst_psum[i] = lst_psum[i-1]+lst[i][1];
        //     fst_idx[i] = fst[i][0];
        //     lst_idx[i] = lst[i][0];
        // }

        // int beg = fst[0][0], ed = lst[len-1][0];
        // vector<int> ans;

        // if(beg>1){
        //     vector<int> zero_pre(beg-1, 0);
        //     ans.insert(ans.begin(), zero_pre.begin(), zero_pre.end());
        // }

        // for(int i=beg; i<=ed; i++){
        //     int fstid = upper_bound(fst_idx.begin(), fst_idx.end(), i)-fst_idx.begin()-1;
        //     int lstid = lower_bound(lst_idx.begin(), lst_idx.end(), i)-lst_idx.begin()-1;

        //     if(lstid<0){
        //         ans.push_back(fst_psum[fstid]);
        //     }
        //     else{
        //         ans.push_back(fst_psum[fstid] - lst_psum[lstid]);
        //     }
        // }

        // if(ed<n){
        //     vector<int> zero_post(n-ed, 0);
        //     ans.insert(ans.end(), zero_post.begin(), zero_post.end());
        // }

        // return ans;
        
    }
};
78500