Thiết kế hệ thống quản lý trạng thái đặt chỗ n ghế (1..n). Cài đặt class SeatReserveManager với:
- Constructor(n): khởi tạo n ghế, ban đầu đều trống.
- reserve(): lấy ghế trống số nhỏ nhất, đặt chỗ, trả về số ghế.
- unreserve(seatNumber): hủy đặt chỗ ghế seatNumber.
Ví dụ: reserve()×3 → 1,2,3; unreserve(2), unreserve(5); reserve()×2 → 2,5.
Giải thuật (Min-heap / Sorted list cho ghế trống)
- current_seat: ghế tiếp theo chưa bao giờ được đặt (tăng dần).
- empty_seats: danh sách ghế đã hủy (cần lấy min). Dùng heapq hoặc min() đơn giản.
- reserve(): nếu empty_seats không rỗng → pop min; else current_seat++.
- unreserve(): push seatNumber vào empty_seats.
Code Python
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)
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
Đầu vào / Đầu ra
Output: 1 2 3 2 5