[LeetCode] 1845. Seat Reservation Manager

https://leetcode.com/problems/seat-reservation-manager/description/

Seat Reservation Manager - LeetCode

leetcode - Seat Reservation Manager

문제 유형 : 우선순위 큐 / 구현

문제 난이도 : Medium

 

문제

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

• SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
• int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
• void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

1부터 n까지 번호가 지정된 n개의 자리 예약을 관리하는 시스템 SeatManager 클래스를 구현하라.

- SeatManager(int n): SeatManager 객체를 초기화한다. n개의 좌석을 만들어줄 수 있고, 처음에는 모두 예약할 수 있다.

- int reserve(): 예약되지 않은 좌석들 중 가장 번호가 낮은 좌석을 예약하고 그 좌석 번호를 반환한다.

- void unreserve(int seatNumber): searNumber번째 자리의 예약을 해지한다.

 

 

풀이

top변수를 만들어서 저장한다. 이 변수는 가장 뒤에 예약된 위치를 저장한다.

우선순위 큐를 만든다. 

unreserve()에서는 seatNumber의 최소 힙 우선순위 큐에 넣는다.

reserve()메서드는 우선순위 큐가 비어있다면 top을 한칸 밀어 맨 뒤에 예약시키고, 

그렇지 않다면, 우선순위 큐에서 pop해서 그 자리부터 예약시킨다.

 

 

코드

C++

class SeatManager {
public:
    priority_queue<int, vector<int>, greater<int>> pq;
    int top = 1;
    SeatManager(int n) {
    }
    
    int reserve() {
        if(pq.empty()) {
            top++;
            return top-1;
        } else {
            int reserved = pq.top();
            pq.pop();
            return reserved;
        }
    }
    
    void unreserve(int seatNumber) {
        pq.push(seatNumber);
    }
};

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager* obj = new SeatManager(n);
 * int param_1 = obj->reserve();
 * obj->unreserve(seatNumber);
 */