LC.P1109[航班预订统计]

方法一：差分数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] d = new int[n];
        for (int[] b : bookings) {
            int first = b[0], last = b[1], seat = b[2];
            d[first - 1] += seat;
            if (last < n) {
                d[last] -= seat;
            }
        }
        for (int i = 1; i < n; ++i) {
            d[i] += d[i - 1];
        }
        return d;
    }
}
  • 时间复杂度：$O(n + m)$
  • 空间复杂度：$O(n)$