{"id":5287,"date":"2019-07-11T09:25:08","date_gmt":"2019-07-11T16:25:08","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5287"},"modified":"2019-07-14T12:30:51","modified_gmt":"2019-07-14T19:30:51","slug":"leetcode-1109-corporate-flight-bookings","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-1109-corporate-flight-bookings\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1109. Corporate Flight Bookings"},"content":{"rendered":"\n

There are n<\/code> flights, and they are labeled from 1<\/code> to n<\/code>.<\/p>\n\n\n\n

We have a list of flight bookings.  The i<\/code>-th booking bookings[i] = [i, j, k]<\/code> means that we booked k<\/code>seats from flights labeled i<\/code> to j<\/code> inclusive.<\/p>\n\n\n\n

Return an array answer<\/code> of length n<\/code>, representing the number of seats booked on each flight in order of their label.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5\nOutput:<\/strong> [10,55,45,25,25]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= bookings.length <= 20000<\/code><\/li>
  • 1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000<\/code><\/li>
  • 1 <= bookings[i][2] <= 10000<\/code><\/li><\/ul>\n\n\n\n
    Solution: Marking start and end<\/strong><\/h2>\n\n\n\n
    Time complexity: O(|bookings|)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector corpFlightBookings(vector>& bookings, int n) {\n    vector ans(n + 1);\n    for (const auto& b : bookings) {\n      ans[b[0] - 1] += b[2];\n      ans[b[1]] -= b[2];\n    }\n    for (int i = 1; i < n; ++i)\n      ans[i] += ans[i - 1];\n    ans.pop_back();\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    There are n flights, and they are labeled from 1 to n. We have a list of flight bookings.  The i-th booking bookings[i] = [i, j, k] means that we booked kseats from flights labeled i to j inclusive.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,177],"class_list":["post-5287","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5287","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5287"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5287\/revisions"}],"predecessor-version":[{"id":5290,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5287\/revisions\/5290"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5287"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}