สมมติว่าเรามี n เที่ยวบิน และมีป้ายกำกับตั้งแต่ 1 ถึง n เรามีรายการจองตั๋วเครื่องบิน การจองครั้งที่ i หมายถึงการใช้การจอง[i] =[i, j, k] ซึ่งหมายความว่าเราจองที่นั่ง k ที่นั่งจากเที่ยวบินที่มีป้ายกำกับว่า i ถึง j ค้นหาคำตอบของอาร์เรย์ของความยาว n โดยแสดงจำนวนที่นั่งที่จองในแต่ละเที่ยวบินตามลำดับป้าย ดังนั้นหากอินพุตเป็น [[1,2,10],[2,3,20],[2,5,25]] และ n =5 ผลลัพธ์จะเป็น [10, 55, 45, 25, 25].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- res :=สร้างอาร์เรย์หนึ่งขนาด n และเติมค่านี้ด้วย 0
- สำหรับแต่ละรายการ i ในการจอง
- res[i[0] - 1] :=res[i[0] - 1] + i[2]
- ถ้า i[1]
- สำหรับ i ในช่วง 1 ถึง n – 1
- res[i] :=res[i] + res[i - 1]
- ผลตอบแทน
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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))
อินพุต
[[1,2,10],[2,3,20],[2,5,25]] 5
ผลลัพธ์
[10, 55, 45, 25, 25]
