Question

1109. 航班预订统计

English Version

题目描述

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

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

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

 

示例 1：

输入：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]

示例 2：

输入：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 * 104
• 1 <= bookings.length <= 2 * 104
• bookings[i].length == 3
• 1 <= firsti <= lasti <= n
• 1 <= seatsi <= 104

解法

方法一：差分数组

我们注意到，每一次预订都是在某个区间 [first, last] 内的所有航班上预订了 seats 个座位。因此，我们可以利用差分数组的思想，对于每一次预订，将 first 位置的数加上 seats，将 last + 1 位置的数减去 seats。最后，对差分数组求前缀和，即可得到每个航班预定的座位总数。

时间复杂度 $O(n)$，其中 $n$ 为航班数。忽略答案的空间消耗，空间复杂度 $O(1)$。

class Solution:
  def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
    ans = [0] * n
    for first, last, seats in bookings:
      ans[first - 1] += seats
      if last < n:
        ans[last] -= seats
    return list(accumulate(ans))

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;
  }
}

class Solution {
public:
  vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> ans(n);
    for (auto& 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;
  }
};

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
}

impl Solution {
  #[allow(dead_code)]
  pub fn corp_flight_bookings(bookings: Vec<Vec<i32>>, n: i32) -> Vec<i32> {
    let mut ans = vec![0; n as usize];

    // Build the difference vector first
    for b in &bookings {
      let (l, r) = ((b[0] as usize) - 1, (b[1] as usize) - 1);
      ans[l] += b[2];
      if r < (n as usize) - 1 {
        ans[r + 1] -= b[2];
      }
    }

    // Build the prefix sum vector based on the difference vector
    for i in 1..n as usize {
      ans[i] += ans[i - 1];
    }

    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;
};

方法二：树状数组 + 差分思想

我们也可以利用树状数组，结合差分的思想，来实现上述操作。我们可以将每一次预订看作是在某个区间 [first, last] 内的所有航班上预订了 seats 个座位。因此，我们可以对每一次预订，对树状数组的 first 位置加上 seats，对树状数组的 last + 1 位置减去 seats。最后，对树状数组每个位置求前缀和，即可得到每个航班预定的座位总数。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为航班数。

以下是树状数组的基本介绍：

树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作：

1. 单点更新 update(x, delta)： 把序列 x 位置的数加上一个值 delta；
2. 前缀和查询 query(x)：查询序列 [1,...x] 区间的区间和，即位置 x 的前缀和。

这两个操作的时间复杂度均为 $O(\log n)$。

class BinaryIndexedTree:
  def __init__(self, n):
    self.n = n
    self.c = [0] * (n + 1)

  def update(self, x, delta):
    while x <= self.n:
      self.c[x] += delta
      x += x & -x

  def query(self, x):
    s = 0
    while x:
      s += self.c[x]
      x -= x & -x
    return s


class Solution:
  def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
    tree = BinaryIndexedTree(n)
    for first, last, seats in bookings:
      tree.update(first, seats)
      tree.update(last + 1, -seats)
    return [tree.query(i + 1) for i in range(n)]

class Solution {
  public int[] corpFlightBookings(int[][] bookings, int n) {
    BinaryIndexedTree tree = new BinaryIndexedTree(n);
    for (var e : bookings) {
      int first = e[0], last = e[1], seats = e[2];
      tree.update(first, seats);
      tree.update(last + 1, -seats);
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      ans[i] = tree.query(i + 1);
    }
    return ans;
  }
}

class BinaryIndexedTree {
  private int n;
  private int[] c;

  public BinaryIndexedTree(int n) {
    this.n = n;
    c = new int[n + 1];
  }

  public void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += x & -x;
    }
  }

  public int query(int x) {
    int s = 0;
    while (x > 0) {
      s += c[x];
      x -= x & -x;
    }
    return s;
  }
}

class BinaryIndexedTree {
public:
  BinaryIndexedTree(int _n)
    : n(_n)
    , c(_n + 1) {}

  void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += x & -x;
    }
  }

  int query(int x) {
    int s = 0;
    while (x) {
      s += c[x];
      x -= x & -x;
    }
    return s;
  }

private:
  int n;
  vector<int> c;
};

class Solution {
public:
  vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    BinaryIndexedTree* tree = new BinaryIndexedTree(n);
    for (auto& e : bookings) {
      int first = e[0], last = e[1], seats = e[2];
      tree->update(first, seats);
      tree->update(last + 1, -seats);
    }
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
      ans[i] = tree->query(i + 1);
    }
    return ans;
  }
};

type BinaryIndexedTree struct {
  n int
  c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
  c := make([]int, n+1)
  return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) update(x, delta int) {
  for x <= this.n {
    this.c[x] += delta
    x += x & -x
  }
}

func (this *BinaryIndexedTree) query(x int) int {
  s := 0
  for x > 0 {
    s += this.c[x]
    x -= x & -x
  }
  return s
}

func corpFlightBookings(bookings [][]int, n int) []int {
  tree := newBinaryIndexedTree(n)
  for _, e := range bookings {
    first, last, seats := e[0], e[1], e[2]
    tree.update(first, seats)
    tree.update(last+1, -seats)
  }
  ans := make([]int, n)
  for i := range ans {
    ans[i] = tree.query(i + 1)
  }
  return ans
}