Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: The Number of the Smallest Unoccupied Chair

Explore how to solve the problem of assigning the smallest available chair efficiently by using two min heaps to manage occupied and free chairs as friends arrive and leave. Understand sorting by arrival, heap operations, and handling dynamic scheduling to optimize chair allocation with O(n log n) time complexity.

We'll cover the following...

Statement

At a party, nn friends, numbered from 00 to n−1n - 1, arrive and leave at different times. There are infinitely many chairs, numbered 00 onwards. Each arriving friend sits on the smallest available chair at that moment.

For example, ...