Skip to main content

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


Comments

Popular posts from this blog

Trie

Trie is a data structure belonging to n-ary trees, which is designed for some specific questions, such as, prefix of strings. (If you have never known what binary tree is, maybe you can check binary tree first before read more about Trie). The fact that there are only 26 different letters greatly reduce the possible choices for each position. Or to make it clear, for each position, there are 26 different choices. In mathematics, it seems to be very large (height^26 for the full tree), but in reality, it is rare to be a full tree for the set of meaningful strings (needs at least height^26 strings to be a full tree!), since the height or length of English words are less than 10 in most cases. Therefore, it is popular in string matching or related operations. Please be noted that the trie structure is not only limited to strings, the same idea can be extended to other data types, such as integer (then it becomes a binary tree, since for bit, there are only two possible values). In the cod...

Dynamic Programming - Hard Level - Question 1

Dynamic Programming - Hard Level - Question 1  Leetcode 1937  Maximum Number of Points with Cost You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix. To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score. However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score. Return the maximum number of points you can achieve. abs(x) is defined as: x for x >= 0. -x for x < 0. Constraints: m == points.length n == points[r].length 1 <= m, n <= 10^5 1 <= m * n <= 10^5 0 <= points[r][c] <= 10^5 Analysis: Based on the description, we can define dp[i][j] as the maximum number of points wit...