โจทย์: มีเที่ยวบิน n เที่ยว (1 ถึง n) และรายการจอง bookings[i] = [i, j, k] หมายถึงจอง k ที่นั่งจากเที่ยวบิน i ถึง j รวมทั้งสองปลาย หาจำนวนที่นั่งที่จองในแต่ละเที่ยวบิน
ตัวอย่าง
Input: [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10, 55, 45, 25, 25]
อัลกอริทึม: Difference Array (Prefix Sum Optimization)
แทนที่จะอัปเดตทุกเที่ยวบินในช่วง (O(n×m)) ใช้ Difference Array:
- สร้างอาร์เรย์
resขนาด n เติม 0 - สำหรับแต่ละ booking [i, j, k]:
res[i-1] += k,res[j] -= k(ถ้า j < n) - คำนวณ prefix sum สะสมเพื่อได้ผลลัพธ์สุดท้าย
ตัวอย่างโค้ด Python
class Solution(object):
def corpFlightBookings(self, bookings, n):
res = [0] * n
# ขั้นตอนที่ 1: มาร์กจุดเริ่มและสิ้นสุด
for i in bookings:
res[i[0] - 1] += i[2] # เริ่มเพิ่มที่ i
if i[1] < n:
res[i[1]] -= i[2] # หยุดเพิ่มหลัง j
# ขั้นตอนที่ 2: Prefix sum สะสม
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))
# Output: [10, 55, 45, 25, 25]
ตัวอย่าง Input/Output
Input: [[1,2,10],[2,3,20],[2,5,25]] 5 Output: [10, 55, 45, 25, 25]
ความซับซ้อน: Time O(n + m), Space O(n) - เร็วกว่าวิธี naive O(n×m) มาก
