Daily LeetCode #2

https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair/description/?envType=daily-question&envId=2024-10-11

Since we need to keep track of seat and people, using priority queue can make each insert or retrieve to O(logn). If we use a array, it requires O(n) for each operation.

Use one pq to record available seats, and another to record leaves of people in format (leave_time, seat).

The whole process is like:

• sort friends based on start time, since we need to operate chronologically.
• the first friend comes and takes a seat, dequeue the smallest seat for him. If he is the target friend, return seat otherwise put his leave time and seat info into another pq.
• the next friend comes and takes a seat. Before dequeueing the smallest available seat for him, we need to release seats if people who took those seats already left. If he is the target friend, return seat otherwise put his leave time and seat info into another pq.
• do the same thing to the rest.

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        // use order to record original index relationship
        Integer[] order = new Integer[times.length];
        for (int i = 0; i < times.length; i++) order[i] = i;

        // use priority queue to store times, sort by arrival time.
        PriorityQueue<int[]> leaveTime = new PriorityQueue<>((a, b) -> a[0] - b[0]); //(leave_time, seat)
        PriorityQueue<Integer> availableSeat = new PriorityQueue<>();

        Arrays.sort(order, (a, b) -> times[a][0] - times[b][0]);

        // initialize chairs; at most = times.length
        for(int i = 0; i < times.length; i++) {
            availableSeat.add(i);
        }

        // loop order, since we need original index to get data
        for (int i : order) {
            // release chairs of left people
            while(!leaveTime.isEmpty() && leaveTime.peek()[0] <= times[i][0]) {
                int seatTaken = leaveTime.poll()[1];
                availableSeat.add(seatTaken);
            }

            int seat = availableSeat.poll();

            if(i == targetFriend) {
                return seat;
            }

            leaveTime.add(new int[]{times[i][1], seat}); // new int[]{a, b}
        }

        return -1;
    }
}

One important thing:

We should not sort param times, because we need to remain its index for further data retrieve. So we should create and do the sort on another array to store the original index to allow us use the correct data.

Safer to use (a, b) -> Integer.compare(times[a][0] - times[b][0])than (a, b) -> times[a][0] - times[b][0].