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)