This is the 31st day of my participation in the August More Text Challenge
Flight booking statistics
There are n flights, and they’re numbered from 1 to n.
Have a flight booking form available in Bookings, The i-bookings [I] = [firsti, lasti, Seatsi] entry in the table bookings[I] = [firsti, lasti, Seatsi] means that seatsi seats were booked for each flight from Firsti to lasti (both firsti and lasti included).
Return an array answer of length N, where answer[I] is the total number of seats booked on flight I.
Example 1:
Bookings = [[1,2,10],[2,3,20],[2,5,25]] n = 5 Answer = [10,55,45, 45,25]Copy the code
Example 2:
Bookings = [[1,2,10],[2,2,15]] And n = 2 [10,25] Answer = [10,25]Copy the code
Tip:
1 <= n <= 2 * 10^4
1 <= bookings.length <= 2 * 10^4
bookings[i].length == 3
1 <= firsti <= lasti <= n
1 <= seatsi <= 10^4
Methods a
Difference:
According to the description of the question, we can simplify it into the following requirements:
On the coordinate axes from 1 to n, add some number x to all numbers on a continuous interval; After doing k of these operations, we ask, what is the magnitude of each of the last coordinates;
When we abstract it, we can see that this is a typical difference problem;
For example, add 2 to each number from 1 to 5. So, we could add 2 to 1, and subtract 2 from 6; Why do you do that? Because, at the end of the day, when we solve for something, we solve for its prefix sum; We add 2 to 1, so when we prefix the sum, it’s the same thing as adding 2 to everything after 1; So, in order to only add 2 between 1 and 5, we have to subtract 2 from 6;
Firsti, lasti, seatsi
class Solution { public int[] corpFlightBookings(int[][] bookings, int n) { int[] res = new int[n]; for (int[] x : bookings) { int st = x[0], ed = x[1], cnt = x[2]; res[st - 1] += cnt; if (ed < n) res[ed] -= cnt; } for (int i = 1; i < n; i ++ ) res[i] += res[i - 1]; return res; }}Copy the code
Time complexity: O(n)
Space complexity: O(1)