Flight Booking Statistics (Item No. 1109)

The title

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:

Enter: bookings = [[1.2.10], [2.3.20], [2.5.25]], n = 5Output:10.55.45.25.25] Flight number1   2   3   4   5Reservation record1 ：   10  10Reservation record2 ：       20  20Reservation record3 ：       25  25  25  25Total seats:10  55  45  25  25Therefore, answer = [10.55.45.25.25]
Copy the code

Example 2:

Enter: bookings = [[1.2.10], [2.2.15]], n = 2Output:10.25] Flight number1   2Reservation record1 ：   10  10Reservation record2 ：       15Total seats:10  25Therefore, answer = [10.25]
Copy the code

Tip:

  • 1 <= n <= 2 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104

link

Leetcode-cn.com/problems/co…

explain

This one, this is a difference array.

Forget about the difference array, how do you normally solve this problem?

The answer is simple: loop over each interval to accumulate the array, adding the values to the array elements within the interval.

There’s nothing to be said for this, as normal people can imagine, but isn’t it a bit too performance-intensive?

Is there a good way to do that, because it’s a little bit of a chore to iterate over the array and add it up every time? Apparently there is — difference arrays.

What is a difference array? In fact, it is a fixed concept, don’t ask why, this is the law summarized by predecessors.

It appears to solve the operation of batch changing values in interval.

An 🌰 :

[8.2.6.3.1]
Copy the code

This is a very simple array, how do you derive a difference array from this array?

Diff [I] = num[I] -num [i-1]

Of course, the first element does not need to be handled. From the second element, the code can be 👇 :

const num = [8.2.6.3.1]
const diff = new Array(num.length)
diff[0] = num[0]
for (let i = 1; i < num.length; i++) {
  diff[i] = num[i] - num[i - 1]}console.log(diff)					// [8, -6, 4, -3, -2]
Copy the code

So we get a difference array, using the difference array can also be derived from the original array, the code can be jiang Aunt 👇 :

const origin = new Array(num.length)
origin[0] = diff[0]
for (let i = 1; i < diff.length; i++) {
  origin[i] = origin[i - 1] + diff[i]
}
console.log(origin)				// [8, 2, 6, 3, 1]
Copy the code

Back to the difference array, it is very convenient to add and subtract interval values in the difference array, for example, to add 3 to the array [I, j] interval, just do the following operations:

diff[i] += 3
diff[j + 1] - =3
Copy the code

So after you derive the difference array back to the original array, you get the cumulative array.

In this problem, there are a large number of related operations, and the time complexity of each operation can be reduced to O(1) by using the difference array, effectively reducing the running time of the code.

Your own answer (violence)

There is nothing to be said for violence, and the code is simple to understand (except that it takes time) 👇 :

var corpFlightBookings = function(bookings, n) {
  const res = new Array(n).fill(0)
  for (const booking of bookings) {
    for (let i = booking[0] - 1; i < booking[1]; i++) {
      res[i] += booking[2]}}return res
};
Copy the code

A Better way (Difference)

Using difference we can write code like 👇 :

var corpFlightBookings = function(bookings, n) {
  const diff = new Array(n + 1).fill(0)
  const nums = new Array(n).fill(0)
  for (const booking of bookings) {
    diff[booking[0]] += booking[2]
    if (booking[1] < n) {
      diff[booking[1] + 1] -= booking[2]
    }
  }
  nums[0] = diff[1]
  for (let i = 2; i <= n; i++) {
    nums[i - 1] = nums[i - 2] + diff[i]
  }
  return nums
};
Copy the code

Because of the first element, the difference array needs to be a bit longer, so it has one more length than NUMs.

In fact, this can be simplified even more, because the original array is 0, so you can directly modify the difference array based on the basis of the new array 👇 :

var corpFlightBookings1 = function(bookings, n) {
  const diff = new Array(n).fill(0)
  for (const booking of bookings) {
    diff[booking[0] - 1] += booking[2]
    if (booking[1] < n) {
      diff[booking[1]] -= booking[2]}}for (let i = 1; i < n; i++) {
    diff[i] += diff[i - 1]}return diff
};
Copy the code

This saves the bookings but requires that the first element in the difference array be truly the first element of n size, so watch out for index changes for bookings.





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)