Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1109.html

1109. Corporate Flight Bookings (Medium)

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

Related Topics:
Array, Math

Solution 1. Heap

// OJ: https://leetcode.com/problems/corporate-flight-bookings/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& A, int n) {
        vector<int> ans(n);
        sort(begin(A), end(A));
        auto cmp = [&](int a, int b) { return A[a][1] > A[b][1]; };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for (int i = 0, j = 0, sum = 0; i < n; ++i) {
            while (q.size() && A[q.top()][1] < i + 1) {
                sum -= A[q.top()][2];
                q.pop();
            }
            while (j < A.size() && A[j][0] <= i + 1 && A[j][1] >= i + 1) {
                q.push(j);
                sum += A[j++][2];
            }
            ans[i] = sum;
        }
        return ans;
    }
};

Solution 2. Diff Array

// OJ: https://leetcode.com/problems/corporate-flight-bookings/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& A, int n) {
        vector<int> ans(n);
        for (auto &v : A) {
            ans[v[0] - 1] += v[2];
            if (v[1] < n) ans[v[1]] -= v[2];
        }
        for (int i = 1; i < n; ++i) ans[i] += ans[i - 1];
        return ans;
    }
};

• Java
• C++
• Python
• Go
• Javascript

• class Solution {
      public int[] corpFlightBookings(int[][] bookings, int n) {
          int[] seats = new int[n];
          for (int[] booking : bookings) {
              int start = booking[0], end = booking[1], count = booking[2];
              seats[start - 1] += count;
              if (end < n)
                  seats[end] -= count;
          }
          for (int i = 1; i < n; i++)
              seats[i] += seats[i - 1];
          return seats;
      }
  }
  
  ############
  
  class Solution {
      public int[] corpFlightBookings(int[][] bookings, int n) {
          int[] ans = new int[n];
          for (var e : bookings) {
              int first = e[0], last = e[1], seats = e[2];
              ans[first - 1] += seats;
              if (last < n) {
                  ans[last] -= seats;
              }
          }
          for (int i = 1; i < n; ++i) {
              ans[i] += ans[i - 1];
          }
          return ans;
      }
  }
  

• // OJ: https://leetcode.com/problems/corporate-flight-bookings/
  // Time: O(NlogN)
  // Space: O(N)
  class Solution {
  public:
      vector<int> corpFlightBookings(vector<vector<int>>& A, int n) {
          vector<int> ans(n);
          sort(begin(A), end(A));
          auto cmp = [&](int a, int b) { return A[a][1] > A[b][1]; };
          priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
          for (int i = 0, j = 0, sum = 0; i < n; ++i) {
              while (q.size() && A[q.top()][1] < i + 1) {
                  sum -= A[q.top()][2];
                  q.pop();
              }
              while (j < A.size() && A[j][0] <= i + 1 && A[j][1] >= i + 1) {
                  q.push(j);
                  sum += A[j++][2];
              }
              ans[i] = sum;
          }
          return ans;
      }
  };
  

• class Solution:
      def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
          delta = [0] * n
          for first, last, seats in bookings:
              delta[first - 1] += seats
              if last < n:
                  delta[last] -= seats
          return list(accumulate(delta))
  
  ############
  
  # 1109. Corporate Flight Bookings
  # https://leetcode.com/problems/corporate-flight-bookings/
  
  class Solution:
      def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
          res = [0] * (n + 1)
          
          for start,end,seats in bookings:
              res[start - 1] += seats
              res[end] -= seats
          
          for i in range(1, n):
              res[i] += res[i - 1]
          
          return res[:-1]
  
  

• func corpFlightBookings(bookings [][]int, n int) []int {
  	ans := make([]int, n)
  	for _, e := range bookings {
  		first, last, seats := e[0], e[1], e[2]
  		ans[first-1] += seats
  		if last < n {
  			ans[last] -= seats
  		}
  	}
  	for i := 1; i < n; i++ {
  		ans[i] += ans[i-1]
  	}
  	return ans
  }
  

• /**
   * @param {number[][]} bookings
   * @param {number} n
   * @return {number[]}
   */
  var corpFlightBookings = function (bookings, n) {
      const ans = new Array(n).fill(0);
      for (const [first, last, seats] of bookings) {
          ans[first - 1] += seats;
          if (last < n) {
              ans[last] -= seats;
          }
      }
      for (let i = 1; i < n; ++i) {
          ans[i] += ans[i - 1];
      }
      return ans;
  };
  
  

All Problems

All Solutions