[Swift]LeetCode1109.航班预订统计|CorporateFlightBookings

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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 k seats from flights labeled i to j inclusive.

Return an array answer of length n, representing the number of seats booked on each flight in order of their label.

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]

Constraints:

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

这里有 n 个航班，它们分别从 1 到 n 进行编号。

我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。

示例：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]

提示：

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

1224ms

 1 class Solution {
 2     func corpFlightBookings(_ bookings: [[Int]], _ n: Int) -> [Int] {
 3         var solution = Array(repeating: 0, count: n)
 4         
 5         for booking in bookings {
 6             solution[booking[0]-1] += booking[2]
 7             if booking[1] < n { solution[booking[1]] -= booking[2] }
 8         }
 9         
10         for i in 1..<n {
11             solution[i] += solution[i-1]
12         }
13         
14         return solution
15     }
16 }

1240ms

 1 class Solution {
 2     func corpFlightBookings(_ bookings: [[Int]], _ n: Int) -> [Int] {
 3         var diff = [Int](repeating: 0, count: n+1)
 4         for book in bookings {
 5             let start = book[0]
 6             let end = book[1]
 7             let count = book[2]
 8             diff[start-1] += count
 9             diff[end] -= count
10         }
11         
12         var result = [Int](repeating: 0, count: n)
13         for i in 0..<n {
14             result[i] = (i - 1 >= 0 ? result[i-1] : 0) + diff[i]
15         }
16         return result
17     }
18 }

1312ms

 1 class Solution {
 2   func corpFlightBookings(_ bookings: [[Int]], _ n: Int) -> [Int] {
 3     var line = [Int](repeating: 0, count: n + 2)
 4     for b in bookings {
 5       line[b[0]] += b[2]
 6       line[b[1] + 1] -= b[2]
 7     }
 8     var res = [Int]()
 9     var r = 0
10     for i in 1...n {
11       r += line[i]
12       res.append(r)
13     }
14     return res
15   }
16 }

Runtime: 1336 ms

Memory Usage: 24.2 MB

 1 class Solution {
 2     func corpFlightBookings(_ bookings: [[Int]], _ n: Int) -> [Int] {
 3         var res:[Int] = [Int](repeating:0,count:n) 
 4         for b in bookings
 5         {
 6             res[b[0] - 1] += b[2]
 7             if b[1] < n
 8             {
 9                 res[b[1]] -= b[2]
10             }
11         }
12         
13         for i in 1..<n
14         {
15            res[i] += res[i - 1] 
16         }
17         return res        
18     }
19 }