The Number of the Smallest Unoccupied Chair

class PartyPlanner {
public:
    int findSmallestChair(vector<vector<int>>& guestTimes, int targetGuest) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> chairQueue;
        int arrivalTime = guestTimes[targetGuest][0];
    
        sort(guestTimes.begin(), guestTimes.end());
    
        int newChairNo = 0;  // Next chair number to be assigned
        set<int> freeChairs;
    
        for (auto guestTime : guestTimes) {
            int arrival = guestTime[0];
            int departure = guestTime[1];
    
            // Release chairs that are now free
            while (!chairQueue.empty() && chairQueue.top().first <= arrival) {
                freeChairs.insert(chairQueue.top().second);
                chairQueue.pop();
            }
    
            int assignedChair;
            // Allocate a free chair or a new chair
            if (!freeChairs.empty()) {
                assignedChair = *freeChairs.begin();
                freeChairs.erase(freeChairs.begin());
            } else {
                assignedChair = newChairNo++;
            }
    
            // Remember when the guest will leave
            chairQueue.push({departure, assignedChair});
    
            // If the current guest is the target, return the assigned chair
            if (arrival == arrivalTime) return assignedChair;
        }
    
        return -1;  // If nothing is found, which shouldn't happen
    }
};

In the C++ solution for finding the smallest unoccupied chair at a party, the program uses sorting, priority queues, and sets to efficiently determine when guests will leave and to keep track of the available chairs. Here are the details of how the solution works:

• First, the solution sorts the list of guest arrival and departure times based on arrival time. This ensures that as you process each guest in order, they are considered from the earliest to the latest arrival.
• A priority queue is used to easily manage the departure events and to order them by the earliest departure time. This helps quickly determine when a chair becomes available as guests leave the party.
• A set of integers is employed to efficiently track the currently free chairs. When guests leave, their chairs are added to this free chair set.

The working mechanism is as follows:

1. Iterate through the sorted list of guest times, processing each guest's arrival.
2. Firstly, check the priority queue to release any chairs from guests who have already left by the current guest's arrival time.
3. Determine a chair for the current arriving guest. If there are chairs in the free chair set, the available one with the smallest number is used. If no chairs are free, the guest is assigned a new chair number.
4. Then, the departure time of the current guest is added to the priority queue, paired with their assigned chair number.
5. If the current guest is the target guest, the assigned chair number is immediately returned.

This solution ensures that each guest is allocated the smallest possible unused chair number efficiently and correctly. The set operation guarantees a quick allocation and deallocation of chairs, while the priority queue manages the order of freeing up the chairs. This combination of data structures provides an optimal solution to manage the guest seating at the party based on their arrival and departure timings.

public class Solution {
    
    public int findMinChair(int[][] schedules, int targetFriendIdx) {
        int targetStart = schedules[targetFriendIdx][0];
        Arrays.sort(schedules, (x, y) -> x[0] - y[0]);
    
        int chairCounter = 0;
        PriorityQueue<int[]> departureQueue = new PriorityQueue<>(
            Comparator.comparingInt(chairs -> chairs[0])
        );
        TreeSet<Integer> freeChairs = new TreeSet<>();
    
        for (int[] schedule : schedules) {
            int start = schedule[0];
            int end = schedule[1];
    
            // Release chairs as they become available
            while (!departureQueue.isEmpty() && departureQueue.peek()[0] <= start) {
                freeChairs.add(departureQueue.poll()[1]);
            }
    
            int assignedChair;
            // Allocate from free chairs or assign a new chair if none are available
            if (!freeChairs.isEmpty()) {
                assignedChair = freeChairs.pollFirst();
            } else {
                assignedChair = chairCounter++;
            }
    
            // Add the departure time and appointed chair to the queue
            departureQueue.add(new int[] { end, assignedChair });
    
            // Return chair if it's the targeted friend's start time
            if (start == targetStart) return assignedChair;
        }
    
        return -1; // Default return if something fails, should never reach here given correct input
    }
}

In this Java solution, you manage seating arrangements based on the arrival and departure times of friends at an event, aiming to find the number of the smallest unoccupied chair for a specific friend. This is achieved using sorting, a priority queue, and a TreeSet, to efficiently manage the state of occupied chairs.

The process is as follows:

1. Extract the start time for the target friend using their index in the schedules array.
2. Sort the schedules array to process friends in order of their arrival.
3. Initialize variables including a chair counter starting from 0, a PriorityQueue for tracking the end times and chair assignments, and a TreeSet to handle the free chairs.
4. Iterate over all schedules:
   • For each schedule, determine the start and end time.
   • Release any chairs from the PriorityQueue that are free before the current friend's start time and add them to the TreeSet.
   • Determine the appropriate chair for the current friend:
     • If there are available chairs in the TreeSet, use the smallest numbered one.
     • If no chairs are available, increment the chair counter and use the next new chair.
   • Record the end time of the current friend along with the assigned chair in the PriorityQueue.
   • If the current schedule start time matches the target friend's start time, return the assigned chair number.

If the solution doesn't encounter the return within the loop, it defaults to returning -1, indicating an error scenario or incorrect input handling. This comprehensive approach ensures optimized handling and seat allocations for friends attending the event, provided the schedules are correct and the input is valid.

class Solution:
    def findSmallestChair(self, times: List[List[int]], friendTarget: int) -> int:
        arrival_time_target = times[friendTarget][0]
        times = sorted(
            [
                (start, end, idx)
                for idx, (start, end) in enumerate(times)
            ]
        )
            
        vacant_chair = 0
        free_chairs = []
        departure_queue = []
    
        for event in times:
            start, end, idx = event
    
            # Clearing chairs that are now free
            while departure_queue and departure_queue[0][0] <= start:
                _, freed_chair = heapq.heappop(departure_queue)
                heapq.heappush(free_chairs, freed_chair)
    
            if free_chairs:
                allocated_chair = heapq.heappop(free_chairs)
            else:
                allocated_chair = vacant_chair
                vacant_chair += 1
    
            # Schedule the time this chair will be free
            heapq.heappush(departure_queue, (end, allocated_chair))
    
            # If current guest is the target friend
            if idx == friendTarget:
                return allocated_chair
    
        return 0

In this solution, the task is to find the smallest unoccupied chair for a specific friend given the times each friend occupies a chair. The Python code uses a class with one method, findSmallestChair, to solve this problem. The method processes a list of start and end times when friends will occupy chairs, and it determines the smallest unoccupied chair number for the target friend.

To understand how the solution works, consider these steps:

1. Extract the arrival time for the target friend directly from the times list using the index friendTarget.
2. Sort times by the start time to process in chronological order of arrival. This optimization ensures we handle chair assignments as guests arrive.
3. To manage free and occupied chairs, use a min heap (free_chairs) for available chairs and another (departure_queue) to track when guests will leave and free up chairs.
4. Traverse through sorted times:
   • If a chair becomes free (i.e., its corresponding end time is before or equal to the start time of the arriving friend), it is moved from departure_queue to free_chairs.
   • Allocate a chair either from free_chairs or assign a new chair if none are available.
   • Record the chair's departure time in departure_queue.
5. If the currently processed arrival belongs to the target friend, immediately return the allocated chair number.
6. If the function exits the loop without finding the target friend, return 0.

This approach provides an efficient way to manage chair assignments using heaps, ensuring minimal time complexity. It specifically sorts the events by starting time and uses priority queues to dynamically retrieve and assign the smallest available chair, ensuring optimal performance for each friend's arrival handling.