Sweep Line - Question 2

1109. Corporate Flight Bookings

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.

Constraints:

1 <= n <= 2 * 10^4

1 <= bookings.length <= 2 * 10^4

bookings[i].length == 3

1 <= firsti <= lasti <= n

1 <= seatsi <= 10^4

Analysis:

The naïve method is to fill in every fight with the number of seats booked. The overall time complexity is O(N^2), which cannot pass the online OJ.

We do not have to do this. Instead, we can just label the starting and ending flights (since all the flights between them are the same).

Or in the terminology of Sweep line, we can treat the flights range as an interval: the start flight is the start of the interval, and end is the end of the interval.

After labeling each interval, we just need to a one-time sweeping of all the flights. The accumulated number of seats at each flight are the number of seat booked for that flight.

Time complexity: O(N)

Space complexity: O(N)

See the code below:

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n, 0), data(n+1, 0);
        for(auto &a : bookings) {
            data[a[0]-1] += a[2];
            data[a[1]] -= a[2];
        }
        for(int i=0; i<n; ++i) {
            res[i] = (i==0?0:res[i-1]) + data[i];
        }
        return res;
    }
};

Upper Layer