[Medium] 1845. Seat Reservation Manager

문제

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(int n) 1부터 n까지 번호가 매겨진 시트를 관리하는 SeatManager 개체를 초기화합니다. 처음에는 모든 좌석을 이용할 수 있습니다.
int reserve() 가장 작은 번호의 예약되지 않은 좌석을 가져오고 예약하며 해당 번호를 반환합니다.
void unreserve(int seatNumber) 지정된 시트 번호로 좌석을 예약 취소합니다.

 

예시

Example 1:

Input
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
Output
[null, 1, 2, null, 2, 3, 4, 5, null]

Explanation
SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats.
seatManager.reserve();    // All seats are available, so return the lowest numbered seat, which is 1.
seatManager.reserve();    // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5].
seatManager.reserve();    // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.reserve();    // The available seats are [3,4,5], so return the lowest of them, which is 3.
seatManager.reserve();    // The available seats are [4,5], so return the lowest of them, which is 4.
seatManager.reserve();    // The only available seat is seat 5, so return 5.
seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].

 

제약 조건

Constraints:

• 1 <= n <= 105
• 1 <= seatNumber <= n
• For each call to reserve, it is guaranteed that there will be at least one unreserved seat.
• For each call to unreserve, it is guaranteed that seatNumber will be reserved.
• At most 105 calls in total will be made to reserve and unreserve.

 

해결 과정

1. SeatManager Class를 초기화 한다.

2. reserve 함수에서 min 자리가 예약 되어 있지 않다면, 현재 min을 res에 할당하고, min의 수를 올린다 (예약한다)

만약 예약이 되어있다면 현재 min 자리의 수를 min으로 할당하고 현재 min을 반환한다.

3. 자리 예약을 취소할 땐, 취소하는 자리의 수와 min의 수를 비교하여 두 가지의 경우로 나눈다.

min의 수보다 자리의 수가 더 작다면 seatNumber와 min을 swap 한다.

 

해결 코드

/**
 * @param {number} n
 */
var SeatManager = function(n) {
    this.min = 1
    this.n = n
    this.seat = []
};

/**
 * @return {number}
 */
SeatManager.prototype.reserve = function() {
    let res = 0;
	
    if( !this.seat[this.min] ){        
        res = this.min;
        this.min = this.n < this.min ? NaN : this.min + 1;

    } else {        
        res = this.min;
        this.min = this.seat[this.min];        
    }
    
    return res;
};

/** 
 * @param {number} seatNumber
 * @return {void}
 */
SeatManager.prototype.unreserve = function(seatNumber) {
    if (this.min < seatNumber ) {        
        let pre_inx = this.min 
        let next_inx = this.seat[this.min]
        
        while(next_inx < seatNumber){
            pre_inx = next_inx
            next_inx = this.seat[next_inx]
        }
        
        [ this.seat[pre_inx], this.seat[seatNumber] ] = [ seatNumber, this.seat[pre_inx] ]
        
    } else {        
        [ this.seat[seatNumber], this.min ] = [ this.min, seatNumber ]        
    }
};

/** 
 * Your SeatManager object will be instantiated and called as such:
 * var obj = new SeatManager(n)
 * var param_1 = obj.reserve()
 * obj.unreserve(seatNumber)
 */