smallest chair [heap]

XXX. Smallest Chair

Greedy

Priority Queue

Problem Statement:

A party is held where friends arrive and leave at specific times. Each friend sits in the smallest-numbered available chair upon arrival. The task is to determine which chair a specific friend (targetFriend) occupies.

Approach:

1. Store all arrival and leave events in a single list. Represent arrival as {arrivalTime, friendIndex} and leave as {leaveTime, -friendIndex} (negative index).
2. Sort all events by time. If two events have the same time, prioritize leave events.
3. Use two priority queues:
   • availableChairs: Tracks the smallest-numbered chairs currently available.
   • occupiedChairs: Tracks the chairs in use and the times when they will be vacated.
4. Process each event:
   • For leave events, free up the corresponding chair by adding it back to availableChairs.
   • For arrival events, assign the smallest available chair and track when it will be vacated.
5. If the current event corresponds to the targetFriend, return the assigned chair.

Algorithm Intuition:

The solution uses a greedy approach to always assign the smallest-numbered available chair. Sorting events ensures that we process them in chronological order. Priority queues efficiently manage available and occupied chairs, allowing us to handle the dynamic nature of the problem.

The negative indexing for leave events helps distinguish between arrival and leave, simplifying the logic. By prioritizing leave events at the same time, chairs are freed before being reassigned.

Complexity:

Time Complexity: O(n log n), where n is the number of events (2 × number of friends).
Space Complexity: O(n), for the priority queues and event storage.

Java Implementation:

// Find the smallest chair assigned to a specific friend
public int smallestChair(int[][] times, int targetFriend) {
    List events = new ArrayList<>(); // To store arrival and leave events

    // Populate events with {time, friendIndex} and {time, ~friendIndex}
    for (int i = 0; i < times.length; i++) {
        events.add(new int[] { times[i][0], i }); // Friend arrives
        events.add(new int[] { times[i][1], ~i }); // Friend leaves
    }

    // Sort events by time; if times are equal, process leaves (-index) before arrivals (+index)
    events.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

    PriorityQueue pq = new PriorityQueue<>(); // Min-heap to manage chairs
    for (int i = 0; i < times.length; i++) {
        pq.add(i); // Initially, all chairs are available
    }

    int[] assignedChairs = new int[times.length]; // Track which chair is assigned to each friend

    for (int[] event : events) {
        int friendIndex = event[1];
        if (friendIndex >= 0) { // Friend arrives
            int chair = pq.poll(); // Assign the smallest available chair
            assignedChairs[friendIndex] = chair; // Record the assigned chair
            if (friendIndex == targetFriend) {
                return chair; // Return the chair for the target friend
            }
        } else { // Friend leaves
            pq.add(assignedChairs[~friendIndex]); // Free up their chair
        }
    }

    return -1; // This line should never be reached
}