ปัญหา
ออกแบบระบบจองที่นั่ง n ที่นั่ง (1 ถึง n) เริ่มต้นว่าทุกที่ รองรับ: Reserve() → ที่นั่งว่างเลขน้อยที่สุด, Unreserve(seatNumber) → ยกเลิกการจอง
ตัวอย่าง
SeatReserveManager(7)
reserve() → 1, reserve() → 2, reserve() → 3
unreserve(2), unreserve(5) (5 ยังไม่จอง)
reserve() → 2, reserve() → 5
อัลกอริทึม (Min-Heap / Sorted Set)
- เก็บ Available Seats ใน Min-Heap (Priority Queue)
- Current Pointer สำหรับที่นั่งใหม่ที่ยังไม่เคยจอง
- Reserve: ถ้า Heap ไม่ว่าง → Pop Min, Else → Current++
- Unreserve: Push เข้า Heap
ตัวอย่างโค้ด
import heapq
class SeatReserveManager:
def __init__(self, n):
self.current_seat = 0
self.empty_seats = [] # Min-heap
def reserve(self):
if self.empty_seats:
return heapq.heappop(self.empty_seats)
self.current_seat += 1
return self.current_seat
def unreserve(self, seatNumber):
heapq.heappush(self.empty_seats, seatNumber)
# Test
obj = SeatReserveManager(7)
print(obj.reserve()) # 1
print(obj.reserve()) # 2
print(obj.reserve()) # 3
obj.unreserve(2)
obj.unreserve(5)
print(obj.reserve()) # 2
print(obj.reserve()) # 5ความซับซ้อน
- Reserve: O(log k) k = จำนวนที่นั่งว่างใน Heap
- Unreserve: O(log k)
- Space: O(k)
ปรับปรุงจากต้นฉบับ: ใช้ Heap แทน List + min() + remove() เพื่อ O(log n) แทน O(n)
