Problem

There are n flights that are labeled from 1 to n.

You are given an array of flight bookings bookings, where bookings[i] = [firsti, lasti, seatsi] represents a booking for flights firsti through lasti (inclusive) with seatsi seats reserved for each flight in the range.

Return an arrayanswer of lengthn , whereanswer[i]is the total number of seats reserved for flighti.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]
Explanation:
Flight labels:        1   2   3   4   5
Booking 1 reserved:  10  10
Booking 2 reserved:      20  20
Booking 3 reserved:      25  25  25  25
Total seats:         10  55  45  25  25
Hence, answer = [10,55,45,25,25]

Example 2

1
2
3
4
5
6
7
8

Input: bookings = [[1,2,10],[2,2,15]], n = 2
Output: [10,25]
Explanation:
Flight labels:        1   2
Booking 1 reserved:  10  10
Booking 2 reserved:      15
Total seats:         10  25
Hence, answer = [10,25]

Constraints

  • 1 <= n <= 2 * 10^4
  • 1 <= bookings.length <= 2 * 10^4
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 10^4

Solution

Method 1 – Prefix Sum (Difference Array) 1

Intuition

Instead of updating every flight in each booking, we can use a difference array to efficiently apply range updates. By marking the start and end+1 of each booking, we can later compute the total seats for each flight using a prefix sum.

Approach

  1. Initialize an array ans of size n with zeros.
  2. For each booking [first, last, seats]:
    • Add seats to ans[first-1].
    • Subtract seats from ans[last] if last < n.
  3. Compute the prefix sum of ans to get the total seats for each flight.
  4. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> ans(n);
        for (auto& b : bookings) {
            ans[b[0]-1] += b[2];
            if (b[1] < n) ans[b[1]] -= b[2];
        }
        for (int i = 1; i < n; ++i) ans[i] += ans[i-1];
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func corpFlightBookings(bookings [][]int, n int) []int {
    ans := make([]int, n)
    for _, b := range bookings {
        ans[b[0]-1] += b[2]
        if b[1] < n {
            ans[b[1]] -= b[2]
        }
    }
    for i := 1; i < n; i++ {
        ans[i] += ans[i-1]
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

class Solution {
    fun corpFlightBookings(bookings: Array<IntArray>, n: Int): IntArray {
        val ans = IntArray(n)
        for (b in bookings) {
            ans[b[0]-1] += b[2]
            if (b[1] < n) ans[b[1]] -= b[2]
        }
        for (i in 1 until n) ans[i] += ans[i-1]
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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
        for i in range(1, n):
            ans[i] += ans[i-1]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn corp_flight_bookings(bookings: Vec<Vec<i32>>, n: i32) -> Vec<i32> {
        let n = n as usize;
        let mut ans = vec![0; n];
        for b in bookings {
            ans[(b[0]-1) as usize] += b[2];
            if b[1] < n as i32 {
                ans[b[1] as usize] -= b[2];
            }
        }
        for i in 1..n {
            ans[i] += ans[i-1];
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    corpFlightBookings(bookings: number[][], n: number): number[] {
        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;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n is the number of flights and m is the number of bookings. Each booking and each flight is processed once.
  • 🧺 Space complexity: O(n), for the answer array.