1109_航班预订统计

难度：中等

题目

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = $[first_i, last_i, seats_i]$ 意味着在从 $first_i$ 到 $last_i$ （包含 $first_i$ 和 $last_i$ ）的 每个航班 上预订了 $seats_i$ 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例

示例一：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]

示例二：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]

提示

  • $1 <= n <= 2 * 10^4$
  • $1 <= bookings.length <= 2 * 10^4$
  • $bookings[i].length == 3$
  • $1 <= first_i <= last_i <= n$
  • $1 <= seats_i <= 10^4$

解题

这道题按照暴力解法可以解，但是时间比较久

image-20220309102623532

1
2
3
4
5
6
7
8
9
public int[] corpFlightBookings(int[][] bookings, int n) {
  int[] ans = new int[n];
  for (int[] booking: bookings){
    for (int i = booking[0]; i <=booking[1]; i++) {
      ans[i-1] += booking[2];
    }
  }
  return ans;
}

因为每次更新 ans 数组都要更新 booking[1]-booking[0]+1 次，所以考虑使用差分的方式减少更新次数，每次只修改变化的数，即每次只更新两个位置（ans[booking[0]-1] 和 ans[booking[1]]）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] corpFlightBookings(int[][] bookings, int n) {
  int[] ans = new int[n];
  for (int[] booking: bookings){
    ans[booking[0]-1]+=booking[2];
    // 对右边界进行判断，越界则无需处理
    if (booking[1]<n){
      ans[booking[1]]-=booking[2];
    }
  }
  for (int i = 1; i < n; i++) {
    ans[i]+=ans[i-1];
  }
  return ans;
}

image-20220309103008049