Corporate Flight Bookings

medium prefix sum difference array range update

Problem

There are n flights labeled 1 to n. Given an array bookings where bookings[i] = [first, last, seats] means seats seats were booked on every flight from first to last inclusive, return an array answer of length n where answer[j] is the total number of seats reserved on flight j + 1.

Inputbookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5

Output[10, 55, 45, 25, 25]

Flight 2 gets 10 + 20 + 25 = 55; flight 5 gets only the third booking's 25.

bookings (rows "first,last,seats"; separate rows with ;)

def corp_flight_bookings(bookings, n):
    diff = [0] * (n + 1)
    for first, last, seats in bookings:
        diff[first - 1] += seats
        diff[last] -= seats
    answer = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        answer[i] = running
    return answer

function corpFlightBookings(bookings, n) {
  const diff = new Array(n + 1).fill(0);
  for (const [first, last, seats] of bookings) {
    diff[first - 1] += seats;
    diff[last] -= seats;
  }
  const answer = new Array(n).fill(0);
  let running = 0;
  for (let i = 0; i < n; i++) {
    running += diff[i];
    answer[i] = running;
  }
  return answer;
}

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n + 1];
        for (int[] b : bookings) {
            diff[b[0] - 1] += b[2];
            diff[b[1]] -= b[2];
        }
        int[] answer = new int[n];
        int running = 0;
        for (int i = 0; i < n; i++) {
            running += diff[i];
            answer[i] = running;
        }
        return answer;
    }
}

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> diff(n + 1, 0);
    for (auto& b : bookings) {
        diff[b[0] - 1] += b[2];
        diff[b[1]] -= b[2];
    }
    vector<int> answer(n, 0);
    int running = 0;
    for (int i = 0; i < n; i++) {
        running += diff[i];
        answer[i] = running;
    }
    return answer;
}

Explanation

Each booking adds the same number of seats to a whole range of flights. Adding to every flight in every range one by one would be slow, so we use a difference array to apply each range in constant time.

For a booking [first, last, seats] we do just two updates: add seats at diff[first - 1] and subtract seats at diff[last]. The -1 converts to 0-based indexing, and the subtraction marks where the booking's effect stops.

After all bookings are recorded, we sweep left to right taking a running prefix sum of diff. At each flight, running is the total of all bookings that cover it, which we store in answer[i].

Example: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5. Flight 2 sits inside all three ranges, so it accumulates 10 + 20 + 25 = 55, while flight 5 only catches the last booking's 25. The result is [10, 55, 45, 25, 25].

We touch each booking twice and sweep the array once, so the work is O(m + n).

Time: O(m + n) Space: O(n)