1109. Corporate Flight Bookings.md

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 bookings[i] = [i, j, k] means that we booked k seats from flights labeled i to j inclusive.

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

• mine

  • Java

    Runtime: 1410 ms, faster than 13.02%, Memory Usage: 54.5 MB, less than 100.00% of Java online submissions

    //O(N^2)time O(N)space
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] res = new int[n];
        for(int i = 0; i < bookings.length; i++){
            for(int j = bookings[i][0]; j <= bookings[i][1]; j++){
                res[j - 1]+= bookings[i][2];
            }
        }
        return res;
    }
    

---

• the most votes

  Runtime: 3 ms, faster than 78.47%, Memory Usage: 55 MB, less than 100.00% of Java online submissions

  //O(N)time O(N)space
  public int[] corpFlightBookings(int[][] bookings, int n) {
      int[] counters = new int[n];
      for (int[] booking : bookings) {
          counters[booking[0] - 1] += booking[2];
          if (booking[1] < n) {
              counters[booking[1]] -= booking[2];
          }
      }
      for (int i = 1; i < n; ++i) {
          counters[i] += counters[i - 1];
      }
      return counters;
  }