1942. The Number of the Smallest Unoccupied Chair
Approach
Min-heaps for free chairs and occupied (endTime, chair) pairs; assign smallest available.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
A heap (priority queue) gives O(log n) insert and O(1) peek with O(log n) removal. In C#, use PriorityQueue<TElement, TPriority> (.NET 6+). Classic patterns: top-K elements (min-heap of size K), merge K sorted lists, Dijkstra's shortest path, and median in a stream (two heaps).
// Approach: Min-heaps for free chairs and occupied (endTime, chair) pairs; assign smallest available.
// Time: O(n log n) Space: O(n)
public class Solution
{
public int SmallestChair(int[][] times, int targetFriend)
{
int nextUnsatChair = 0;
PriorityQueue<int, int> emptyChairs = new PriorityQueue<int, int>();
PriorityQueue<(int, int), int> occupied = new PriorityQueue<(int, int), int>(Comparer<int>.Create((a, b) => a.CompareTo(b)));
for (int i = 0; i < times.Length; ++i)
{
Array.Resize(ref times[i], times[i].Length + 1);
times[i][times[i].Length - 1] = i;
}
Array.Sort(times, (a, b) => a[0].CompareTo(b[0]));
foreach (var time in times)
{
int arrival = time[0];
int leaving = time[1];
int i = time[2];
while (occupied.Count > 0 && occupied.Peek().Item1 <= arrival)
{
int occupiedChair = occupied.Dequeue().Item2;
emptyChairs.Enqueue(occupiedChair, occupiedChair);
}
if (i == targetFriend)
return emptyChairs.Count == 0 ? nextUnsatChair : emptyChairs.Peek();
if (emptyChairs.Count == 0)
{
occupied.Enqueue((leaving, nextUnsatChair), leaving);
nextUnsatChair++;
}
else
{
int emptyChair = emptyChairs.Dequeue();
occupied.Enqueue((leaving, emptyChair), leaving);
}
}
throw new ArgumentException();
}
}