⚡Flashcard Drill➔
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

  1. Process friends in arrival order, maintaining a min-heap of free chairs and a min-heap of (leaveTime, chair) for occupied ones.
  2. Before each arrival, release every occupied chair whose leave time is at or before the arrival.
  3. Assign the smallest free chair; if the friend is the target, return it immediately.
  4. 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 n chairs: at most n friends are present, so chairs 0..n-1 suffice.
  • 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.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems