The Number of the Smallest Unoccupied Chair

The Number of the Smallest Unoccupied Chair

What is this problem about?

Imagine a group of friends arriving at a party where chairs are numbered starting from 0. Each person arrives at a specific time and stays until a specific leaving time. When someone arrives, they always sit in the unoccupied chair with the smallest number. When they leave, their chair becomes unoccupied immediately. Given the arrival and leaving times of all guests and a specific "target friend," find the chair number that the target friend will sit in.

Why is this asked in interviews?

This the Number of the Smallest Unoccupied Chair interview question is asked by companies like Microsoft, Amazon, and Google. It tests your ability to manage multiple dynamic events using efficient data structures. Specifically, it evaluates whether you can use a priority queue (heap) to keep track of available chairs and another heap to manage when guests leave and free up their chairs. It is a classic example of event-driven simulation.

Algorithmic pattern used

The problem utilizes the Array, Hash Table, Heap (Priority Queue) interview pattern.

1. Sort all guests by their arrival time. Keep track of the original index to identify the "target friend."
2. Use a min-heap availableChairs to store all chairs that are currently free (initially 0, 1, 2, ... up to n).
3. Use another min-heap occupiedUntil to store (leaving_time, chair_number) for guests currently sitting.
4. For each guest:
   • While the top of occupiedUntil has a leaving time <= current guest's arrival time, pop it and add the chair_number back to availableChairs.
   • Pop the smallest chair from availableChairs and assign it to the current guest.
   • If the current guest is the "target friend," return the assigned chair number.
   • Otherwise, push (leaving_time, assigned_chair) into occupiedUntil.

Example explanation

Target Friend Index: 0. Arrivals: [[1, 4], [2, 3], [4, 6]]. Sorted: Guest 0 (1,4), Guest 1 (2,3), Guest 2 (4,6).

1. Guest 0 (Time 1): Smallest chair is 0. Since this is the target, return 0. Wait, let's try if Target was 2.
2. Guest 0 (Time 1): Takes chair 0. Occupied: {(4, 0)}.
3. Guest 1 (Time 2): Smallest chair is 1. Takes chair 1. Occupied: {(3, 1), (4, 0)}.
4. Time 3: Guest 1 leaves. Chair 1 is now available.
5. Guest 2 (Time 4): Before sitting, Guest 0 also leaves (Time 4). Chair 0 is now available. Available chairs: {0, 1}.
6. Guest 2 takes chair 0. Return 0.

Common mistakes candidates make

In "The Number of the Smallest Unoccupied Chair coding problem," a common mistake is not releasing chairs before the current guest sits down. If a guest leaves exactly when another arrives, the chair should be available. Another mistake is using a simple list and searching for the minimum chair, which leads to O(n^2) complexity, whereas heaps provide O(n log n).

Interview preparation tip

Priority queues are essential for managing "the smallest" or "the largest" item in a dynamic set. Practice using two heaps together—one for available resources and one for active tasks—as this is a recurring pattern in resource allocation problems.