LeetCode Q 1109 - Corporate Flight Bookings

There are n flights, and they are labeled from 1 to n.
We have a list of flight bookings. The i-th booking ookings[i] = [i, j, k] means that we booked k seats from flights labeled i to jinclusive.
Return an array answer of length n, representing the number of seats booked on each flight in order of their label.

Example 1:
Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 ; Output: [10,55,45,25,25]

Constraints:

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

Solution:

Solution 1: A Brute Force Solution

Code:

public int[] corpFlightBookings(int[][] bookings, int n) {
  int[] res = new int[n];

  for (int[] booking: bookings) {
    for (int i = booking[0]; i <= booking[1]; i++) 
      res[i] += booking[k];
  }

  return res;
}

Solution 2: A much more effecient way O(n)

We firstly use array res to store the numbers we should add or minus at a stop. Then from 1 to n accumulate the sum and update res[i].

Code:

public int[] corpFlightBookings(int[][] bookings, int n) {
  int[] res = new int[n];

  for (int[] booking: bookings) {
    res[booking[0]] += booking[2];
    if (booking[1] < n) res[booking[1]] -= booking[2];
  }

  for (int i = 1; i < n; i++) res[i] += res[i - 1];
  
  return res;
}

Reprint policy