NeetCode #842LC-1942MediumIntervals
← Back to All Problems#842 · #1942 · The Number of the Smallest Unoccupied Chair(最小未被占据椅子的编号)
📌 Problem Statement & Constraints
There are infinitely many chairs numbered
0, 1, 2, .... Friends arrive at times[i][0] and leave at times[i][1], and each sits on the smallest-numbered free chair. Return the chair that targetFriend sits on. All arrival times are distinct. Constraints: 1 <= times.length <= 10^4, 0 <= times[i][0] < times[i][1] <= 10^5, 0 <= targetFriend < times.length.💡 Core Algorithmic Approaches
- Process friends in arrival order, maintaining a min-heap of free chairs and a min-heap of
(leaveTime, chair)for occupied ones. - Before each arrival, release every occupied chair whose leave time is at or before the arrival.
- Assign the smallest free chair; if the friend is the target, return it immediately.
- Because arrivals are processed in time order, this simulation matches the physical process exactly.
💻 Benchmark Python3 Implementation
class Solution:
def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
import heapq
order = sorted(range(len(times)), key=lambda i: times[i][0])
free = list(range(len(times))) # at most n chairs are ever needed
heapq.heapify(free)
busy = [] # (leave time, chair)
for i in order:
arrive, leave = times[i]
while busy and busy[0][0] <= arrive:
_, c = heapq.heappop(busy)
heapq.heappush(free, c) # chair is free again
chair = heapq.heappop(free)
if i == targetFriend:
return chair
heapq.heappush(busy, (leave, chair))
return -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): sorting the friends plus heap operations.
💾 Space Complexity
O(n): the two heaps.
⚠️ Interview Pitfalls & Follow-ups
- Using
busy[0][0] < arrive: a friend leaving exactly at the arrival time frees the chair, so the test is<=. - Allocating more than
nchairs: at mostnfriends are present, so chairs0..n-1suffice. - Processing in the original array order: friends must be seated in arrival order, which requires sorting by arrival time.
- Returning after the whole loop: the target must be captured the moment it is seated, because later friends may take other chairs.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.