📚 The Number of the Smallest Unoccupied Chair – Java Cheat Sheet

📌 What Is It?

The problem involves finding the smallest unoccupied chair for a specific friend arriving at a party. Each friend has an arrival and departure time, and chairs are assigned in increasing order starting from 0. When a chair becomes unoccupied, it can be reassigned to another friend.

To solve this efficiently, we use two heaps:

Min-Heap 1: Tracks the smallest available chairs.
Min-Heap 2: Tracks the departure times of occupied chairs.

🧱 Pattern Template

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int n = times.length;
        int targetArrival = times[targetFriend][0];

        // Step 1: Sort times by arrival time
        int[][] indexedTimes = new int[n][3];
        for (int i = 0; i < n; i++) {
            indexedTimes[i][0] = times[i][0]; // Arrival time
            indexedTimes[i][1] = times[i][1]; // Departure time
            indexedTimes[i][2] = i; // Friend index
        }
        Arrays.sort(indexedTimes, (a, b) -> a[0] - b[0]);

        // Step 2: Initialize heaps
        PriorityQueue availableChairs = new PriorityQueue<>();
        PriorityQueue occupiedChairs = new PriorityQueue<>((a, b) -> a[0] - b[0]); // [departureTime, chair]

        // Add all chairs to the availableChairs heap
        for (int i = 0; i < n; i++) {
            availableChairs.offer(i);
        }

        // Step 3: Process each friend
        for (int[] time : indexedTimes) {
            int arrival = time[0];
            int departure = time[1];
            int friendIndex = time[2];

            // Free up chairs that have been vacated
            while (!occupiedChairs.isEmpty() && occupiedChairs.peek()[0] <= arrival) {
                availableChairs.offer(occupiedChairs.poll()[1]);
            }

            // Assign the smallest available chair
            int chair = availableChairs.poll();
            if (friendIndex == targetFriend) {
                return chair;
            }

            // Mark the chair as occupied
            occupiedChairs.offer(new int[]{departure, chair});
        }

        return -1; // Should never reach here
    }
}

📊 Time Complexity

Sorting Times: O(n log n) – Sorting the arrival times.
Heap Operations: O(n log n) – Adding and removing elements from heaps for n friends.
Overall Complexity: O(n log n).

✅ Use Cases

Scheduling problems with limited resources
Efficiently assigning resources based on availability
Applications in event management and resource allocation

📘 Common LeetCode Problems

1942. The Number of the Smallest Unoccupied Chair [Medium] Heap

🧪 Example: The Number of the Smallest Unoccupied Chair

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1

Explanation:
- Friend 0 arrives at 1 and takes chair 0.
- Friend 1 arrives at 2 and takes chair 1.
- Friend 0 leaves at 4, freeing chair 0.
- Friend 2 arrives at 4 and takes chair 0.
- Target friend (1) is assigned chair 1.

💡 Pro Tips

Use a min-heap to efficiently track the smallest available chairs.
Edge cases: overlapping arrival and departure times, single friend.
Ensure the heaps are updated correctly when chairs are vacated.