[leetcode daily question 2021/8/31] 1109. Flight reservation statistics [medium] differential array

The title comes from leetcode, Solutions and ideas represent only personal views . Portal .
difficulty ： secondary
Time ：-
TAG： Difference array

subject

Here you are n A flight , They are from 1 To n Number .

There is a flight reservation form bookings , No i Booking records bookings[i] = [firsti, lasti, seatsi] Means from firsti To lasti （ contain firsti and lasti ） Of Every flight I made a reservation on seatsi A seat .

Please return a length of n Array of answer, among answer[i] It's a flight i The total number of seats booked on .

Example 1：

 Input ：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
 Output ：[10,55,45,25,25]
 explain ：
 Flight number         1   2   3   4   5
 Booking records  1 ：   10  10
 Booking records  2 ：       20  20
 Booking records  3 ：       25  25  25  25
 Total number of seats ：      10  55  45  25  25
 therefore ,answer = [10,55,45,25,25]

Example 2：

 Input ：bookings = [[1,2,10],[2,2,15]], n = 2
 Output ：[10,25]
 explain ：
 Flight number         1   2
 Booking records  1 ：   10  10
 Booking records  2 ：       15
 Total number of seats ：      10  25
 therefore ,answer = [10,25]

Tips ：

1 <= n <= 2 * 10⁴
1 <= bookings.length <= 2 * 10⁴
bookings[i].length== 3
1 <= first_i <= last_i <= n
1 <= seats_i <= 104

Ideas

leetcode Original problem solution

If you generate a two-dimensional array to save bookings, In the accumulation . Then it will definitely time out .

We need a way , Maintain a section , Make in A section Modification of interval , Make it easy . And it can get , Section Some The value of the location .

This method is Difference array .

Difference array

Definition of differential array ？

For arrays [1,2,2,4], The difference score group is [1,1,0,2], The second... Of the difference array $i$ The number is the... Of the original array $i-1$ Elements and number $i$ The difference between elements .

Characteristics of differential array ？

• Find The prefix and You can get the original array .（ Prefixes and can Modify in place Original array ）.
• When we want to set an interval of the original array $[l,r]$ Apply an increment $inc$ when , Difference array $d$ The corresponding change is ：$d[l]$ increase $inc$,$d[r+1]$ Reduce $inc$. In this way, the modification of the interval becomes the modification of two positions .

Code

class Solution {
    
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    
        // Interval query 
        vector<int> ans(n+1);
        for(auto &booking:bookings){
    
            int first = booking[0];
            int last = booking[1];
            int seats = booking[2];
            ans[first-1] += seats;
            ans[last] -= seats;
        }
        // Calculate the prefix and 
        for(int i=1;i<n;i++){
    
            ans[i] += ans[i-1];
        }
        ans.pop_back();
        return ans;
    }
};

Algorithm complexity

Time complexity ： O(n+m).n Is the number of flights ,m by bookings The length of .
Spatial complexity ： O(n).n Is a differential array ans length .