Seat Manager == Priority Queue

This problem just requires a direct implementation of a Priority Queue, take a look: Seat Reservation Manager - LeetCode

1845. 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.

 

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.

Accepted

5,450

Submissions

10,477

It is a direct implementation of Priority Queue. Code is down below, cheers, ACC.

    public class SeatManager
    {
        private PriorityQueue pQueue = null;
        public SeatManager(int n)
        {
            pQueue = new PriorityQueue(true);

            for (int i = 1; i <= n; i++)
            {
                pQueue.Enqueue(i, i);
            }
        }

        public int Reserve()
        {
            return (int)pQueue.Dequeue();
        }

        public void Unreserve(int seatNumber)
        {
            pQueue.Enqueue(seatNumber, seatNumber);
        }
    }

    public class PriorityQueue
    {
        public struct HeapEntry
        {
            private object item;
            private double priority;
            public HeapEntry(object item, double priority)
            {
                this.item = item;
                this.priority = priority;
            }
            public object Item
            {
                get
                {
                    return item;
                }
            }
            public double Priority
            {
                get
                {
                    return priority;
                }
            }
        }

        private bool ascend;
        private int count;
        private int capacity;
        private HeapEntry[] heap;

        public int Count
        {
            get
            {
                return this.count;
            }
        }

        public PriorityQueue(bool ascend)
        {
            capacity = 1000000;
            heap = new HeapEntry[capacity];
            this.ascend = ascend;
        }

        public object Dequeue(/*out double priority*/)
        {
            //priority = heap[0].Priority;
            object result = heap[0].Item;
            count--;
            trickleDown(0, heap[count]);
            return result;
        }

        public object Peak(/*out double priority*/)
        {
            //priority = heap[0].Priority;
            object result = heap[0].Item;
            return result;
        }

        public void Enqueue(object item, double priority)
        {
            count++;
            bubbleUp(count - 1, new HeapEntry(item, priority));
        }

        private void bubbleUp(int index, HeapEntry he)
        {
            int parent = (index - 1) / 2;
            // note: (index > 0) means there is a parent
            if (this.ascend)
            {
                while ((index > 0) && (heap[parent].Priority > he.Priority))
                {
                    heap[index] = heap[parent];
                    index = parent;
                    parent = (index - 1) / 2;
                }
                heap[index] = he;
            }
            else
            {
                while ((index > 0) && (heap[parent].Priority < he.Priority))
                {
                    heap[index] = heap[parent];
                    index = parent;
                    parent = (index - 1) / 2;
                }
                heap[index] = he;
            }
        }

        private void trickleDown(int index, HeapEntry he)
        {
            int child = (index * 2) + 1;
            while (child < count)
            {
                if (this.ascend)
                {
                    if (((child + 1) < count) &&
                        (heap[child].Priority > heap[child + 1].Priority))
                    {
                        child++;
                    }
                }
                else
                {
                    if (((child + 1) < count) &&
                        (heap[child].Priority < heap[child + 1].Priority))
                    {
                        child++;
                    }
                }
                heap[index] = heap[child];
                index = child;
                child = (index * 2) + 1;
            }
            bubbleUp(index, he);
        }
    }