Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1845.html

1845. Seat Reservation Manager

Level

Medium

Description

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.

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 <= 10^5
  • 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 10^5 calls in total will be made to reserve and unreserve.

Solution

Maintain curr to store the seat to be reserved. Use a tree set to store unreserved seats.

For the constructor, initialize curr = 1 and initialize the tree set.

For reserve, if the tree set is not empty, then use the smallest element in the tree set as the reserved seat and remove it from the tree set. Otherwise, use curr as the reserved seat and increase curr by 1.

For unreserve, add seatNumber to the tree set.

  • class SeatManager {
    int n;
    int curr;
    TreeSet<Integer> set;

    public SeatManager(int n) {
        this.n = n;
        curr = 1;
        set = new TreeSet<Integer>();
    }
    
    public int reserve() {
        if (!set.isEmpty()) {
            int reserveSeat = set.first();
            set.remove(reserveSeat);
            return reserveSeat;
        } else {
            int reserveSeat = curr;
            curr++;
            return reserveSeat;
        }
    }
    
    public void unreserve(int seatNumber) {
        set.add(seatNumber);
    }
}

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

############

class SeatManager {
    private PriorityQueue<Integer> q = new PriorityQueue<>();

    public SeatManager(int n) {
        for (int i = 1; i <= n; ++i) {
            q.offer(i);
        }
    }

    public int reserve() {
        return q.poll();
    }

    public void unreserve(int seatNumber) {
        q.offer(seatNumber);
    }
}

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

  • // OJ: https://leetcode.com/problems/seat-reservation-manager/
// Time:
//      SeatManager: O(1)
//      reserve: O(1)
//      unreserve: O(logN)
// Space: O(U) where U is the number of unreserves.
class SeatManager {
    set<int> unr;
    int cur = 0;
public:
    SeatManager(int n) {}
    int reserve() {
        if (unr.size()) {
            int r = *unr.begin();
            unr.erase(r);
            return r;
        }
        return ++cur;
    }
    void unreserve(int seatNumber) {
        unr.insert(seatNumber);
    }
};

  • class SeatManager:
    def __init__(self, n: int):
        self.q = [i for i in range(1, n + 1)]

    def reserve(self) -> int:
        return heappop(self.q)

    def unreserve(self, seatNumber: int) -> None:
        heappush(self.q, seatNumber)


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

############

# 1845. Seat Reservation Manager
# https://leetcode.com/problems/seat-reservation-manager/

class SeatManager:

    def __init__(self, n: int):
        self.heap = [i for i in range(1, n + 1)]

    def reserve(self) -> int:
        return heapq.heappop(self.heap)

    def unreserve(self, seatNumber: int) -> None:
        heapq.heappush(self.heap, seatNumber)


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


  • type SeatManager struct {
	q hp
}

func Constructor(n int) SeatManager {
	q := hp{}
	for i := 1; i <= n; i++ {
		heap.Push(&q, i)
	}
	return SeatManager{q}
}

func (this *SeatManager) Reserve() int {
	return heap.Pop(&this.q).(int)
}

func (this *SeatManager) Unreserve(seatNumber int) {
	heap.Push(&this.q, seatNumber)
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool  { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

/**
 * Your SeatManager object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Reserve();
 * obj.Unreserve(seatNumber);
 */

  • public class SeatManager {
    private SortedSet<int> availableSeats;

    public SeatManager(int n) {
        availableSeats = new SortedSet<int>();
        for (int i = 1; i <= n; i++) {
            availableSeats.Add(i);
        }
    }
    
    public int Reserve() {
        int reservedSeat = availableSeats.Min;
        availableSeats.Remove(reservedSeat);
        return reservedSeat;
    }
    
    public void Unreserve(int seatNumber) {
        availableSeats.Add(seatNumber);
    }
}

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager obj = new SeatManager(n);
 * int param_1 = obj.Reserve();
 * obj.Unreserve(seatNumber);
 */

All Problems

All Solutions