Problem Statement

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 array answer of length n, where answer[i] is the total number of seats reserved for flight i.

LeetCode

https://leetcode.com/problems/corporate-flight-bookings/description/

Constraints

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

Examples

Example 1:

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:

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]

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Loop through each booking, and for each flight in the range [first_i, last_i], add seats_i to that flight's booking count.

🔧 Approach:

1. Create a result array of size n initialized with 0.
2. For each booking:
   1. Loop from first_i - 1 to last_i - 1
   2. Add seats_i to each of those indexes in the result array.
3. Return the result array.

Code:

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> result(n, 0);

        for (auto& booking : bookings) {
            int start = booking[0];
            int end = booking[1];
            int seats = booking[2];

            // Add seats to each flight in the range [start, end]
            for (int i = start - 1; i <= end - 1; i++) {
                result[i] += seats;
            }
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity:O(m * k), where m = number of bookings and k = average range of updates (can go up to n)
  • Worst case: O(m * n)
• Space Complexity:O(n)
  • For result array

2️⃣ Difference Array Approach (Optimal)

Intuition:

Instead of updating each index in the range [start, end], we mark the start and end of the effect, and later compute the cumulative result using prefix sums.

✨ Concept:

Use a difference array:

• result[start - 1] += seats
• result[end] -= seats (only if end < n)
• Then, compute prefix sum on the result array.

🔧 Steps:

1. Initialize result array of size n with 0
2. For each booking:
   1. Add seats to result[first_i - 1]
   2. Subtract seats from result[lasti] (only if lasti < n)
3. Do a prefix sum over result
4. Return result.

Code:

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        // Step 1: Initialize a result array of size 'n' with all 0s
        // This will store the net seat bookings for each flight.
        vector<int> result(n, 0);

        // Step 2: Process each booking
        for (auto& booking : bookings) {
            int start = booking[0] - 1; // Convert 1-based index to 0-based
            int end = booking[1];       // Note: We use this as (end + 1) index
            int seats = booking[2];     // Number of seats booked in this range

            // Add seats to the start index (inclusive)
            result[start] += seats;

            // Subtract seats at index after end (to stop adding beyond end)
            if (end < n) {
                result[end] -= seats;
            }
        }

        // Step 3: Convert the difference array to actual seat bookings
        // by computing prefix sum
        for (int i = 1; i < n; i++) {
            result[i] += result[i - 1];
        }

        // Step 4: Return the final result array
        // Each element now contains the total booked seats for that flight
        return result;
    }
};

Complexity Analysis:

• Time Complexity:O(m + n) where m = bookings.size(), n = number of flights
  • Very efficient even for large inputs.
• Space Complexity:O(n)