Giả sử có n chuyến bay, được gán nhãn từ 1 đến n. Ta có danh sách đặt chỗ chuyến bay. Phần tử thứ i booking[i] = [i, j, k] có nghĩa là đặt k ghế từ chuyến bay i đến j bao gồm cả hai. Tìm mảng kết quả độ dài n, cho biết số ghế đặt trên mỗi chuyến bay theo thứ tự nhãn. Nếu đầu vào [[1,2,10],[2,3,20],[2,5,25]] và n = 5, kết quả [10, 55, 45, 25, 25].
Để giải quyết, ta làm theo các bước −
- res := mảng độ dài n, điền 0
- với mỗi entry i trong bookings
- res[i[0] - 1] := res[i[0] - 1] + i[2]
- nếu i[1] < n, res[i[1]] := res[i[1]] - i[2]
- với i từ 1 đến n-1
- res[i] := res[i] + res[i - 1]
- trả về res
Xem triển khai sau −
Ví dụ
class Solution(object): def corpFlightBookings(self, bookings, n): res = [0 for i in range(n)] for i in bookings: res[i[0]-1]+=i[2] if(i[1]<n): res[i[1]]-=i[2] for i in range(1,n): res[i]+=res[i-1] return res ob = Solution() print(ob.corpFlightBookings([[1,2,10],[2,3,20],[2,5,25]],5))
Đầu vào
[[1,2,10],[2,3,20],[2,5,25]] 5
Kết quả
[10, 55, 45, 25, 25]