LeetCode 1942 - The Number of the Smallest Unoccupied Chair

LeetCode Problem 1942

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Heap (Priority Queue)

Solution

Problem Understanding

This problem describes a scenario where a group of friends attends a party with an infinite number of chairs labeled from 0 upwards. Each friend has a specific arrival and leaving time. When a friend arrives, they must occupy the smallest-numbered unoccupied chair. When they leave, that chair becomes free immediately and can be taken by another friend who arrives at that exact moment.

The input times is a 2D array where times[i] = [arrivali, leavingi] gives the arrival and departure times of friend i. targetFriend identifies which friend we want to track to find which chair they occupy. The expected output is a single integer representing the chair number assigned to that friend.

Constraints tell us there can be up to 10^4 friends and that arrival times are distinct. This ensures that sorting by arrival time is safe and that there are no simultaneous arrivals to handle explicitly, simplifying the scheduling. However, the maximum leaving time can be up to 10^5, which means we need an efficient way to track chair occupancy without iterating over every possible chair. Important edge cases include friends arriving at the same moment another leaves and very large or minimal ranges of arrival and departure times.

Approaches

Brute Force

A brute-force solution would simulate every time step from the earliest arrival to the latest departure. For each friend’s arrival, we would iterate through all chairs starting from 0 to find the first unoccupied one. When a friend leaves, we mark their chair as free. This approach is correct but inefficient, because iterating through all chairs for every friend would be too slow for n = 10^4.

Optimal

The key insight for a better solution is to maintain two priority queues. One min-heap tracks available chair numbers, and the other tracks occupied chairs ordered by leaving time. Sorting friends by arrival time ensures we process events chronologically. When a friend arrives, we first free up chairs from any friends who have already left. We then assign the smallest available chair to the new friend. This avoids iterating over all chair numbers, ensuring efficient allocation and deallocation in logarithmic time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Iterates through all chairs to find the smallest free one for each friend
Optimal	O(n log n)	O(n)	Uses min-heaps for efficient chair allocation and release

Algorithm Walkthrough

Sort friends by arrival time to process events chronologically. Each friend record includes their original index to track targetFriend.
Initialize two min-heaps: one for free chairs, initially empty, and one for occupied chairs, storing tuples (leaving time, chair number).
Track the maximum chair number used. Whenever a friend cannot reuse a free chair, assign the next largest chair number.
Iterate through each friend in order of arrival:

a. While the earliest occupied chair’s leaving time is less than or equal to the current friend’s arrival, pop it from the occupied heap and push its chair number onto the free chairs heap.

b. If there are free chairs available, pop the smallest chair number from the free heap and assign it to the friend. Otherwise, assign the next maximum chair number.

c. Push (leaving time, chair number) of this friend onto the occupied heap.

d. If this friend is targetFriend, return the chair number immediately. 5. The algorithm stops when targetFriend is assigned a chair.

Why it works: The algorithm maintains the invariant that the free chairs heap always contains all chairs that have become available before the current arrival. This ensures that the smallest-numbered available chair is always assigned, correctly simulating the party seating rules.

Python Solution

from typing import List
import heapq

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        # Annotate each friend with their index
        friends = [(arr, leave, i) for i, (arr, leave) in enumerate(times)]
        friends.sort(key=lambda x: x[0])  # Sort by arrival time

        free_chairs = []  # min-heap of available chair numbers
        occupied_chairs = []  # min-heap of (leaving time, chair number)
        next_chair = 0  # Next unassigned chair number

        for arr, leave, idx in friends:
            # Free chairs from friends who have already left
            while occupied_chairs and occupied_chairs[0][0] <= arr:
                _, chair_num = heapq.heappop(occupied_chairs)
                heapq.heappush(free_chairs, chair_num)

            # Assign chair
            if free_chairs:
                chair_num = heapq.heappop(free_chairs)
            else:
                chair_num = next_chair
                next_chair += 1

            # Track occupied chair
            heapq.heappush(occupied_chairs, (leave, chair_num))

            # Return if target friend
            if idx == targetFriend:
                return chair_num

Explanation: First, friends are sorted by arrival time. For each friend, the occupied chairs heap is checked for any friends who have left, freeing their chairs. The smallest available chair is chosen from the free chairs heap, or the next new chair is assigned if none are free. The chair assignment is pushed onto the occupied heap for future release tracking. As soon as targetFriend receives a chair, the solution returns it.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

type Friend struct {
	arrival, leaving, index int
}

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

type OccupiedHeap [][2]int // [leaving, chair]

func (h OccupiedHeap) Len() int           { return len(h) }
func (h OccupiedHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h OccupiedHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *OccupiedHeap) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}
func (h *OccupiedHeap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func smallestChair(times [][]int, targetFriend int) int {
	n := len(times)
	friends := make([]Friend, n)
	for i := 0; i < n; i++ {
		friends[i] = Friend{times[i][0], times[i][1], i}
	}
	sort.Slice(friends, func(i, j int) bool { return friends[i].arrival < friends[j].arrival })

	freeChairs := &IntHeap{}
	heap.Init(freeChairs)
	occupiedChairs := &OccupiedHeap{}
	heap.Init(occupiedChairs)
	nextChair := 0

	for _, f := range friends {
		// Free chairs
		for occupiedChairs.Len() > 0 && (*occupiedChairs)[0][0] <= f.arrival {
			leavingChair := heap.Pop(occupiedChairs).([2]int)[1]
			heap.Push(freeChairs, leavingChair)
		}

		// Assign chair
		var chair int
		if freeChairs.Len() > 0 {
			chair = heap.Pop(freeChairs).(int)
		} else {
			chair = nextChair
			nextChair++
		}

		heap.Push(occupiedChairs, [2]int{f.leaving, chair})

		if f.index == targetFriend {
			return chair
		}
	}
	return -1
}

Explanation: The Go version mirrors the Python logic using slices and custom heaps. IntHeap and OccupiedHeap implement the min-heap interface. Chairs are allocated from freeChairs or nextChair, and released chairs are pushed back onto the free heap. Go-specific handling ensures type safety and interface compliance.

Worked Examples

Example 1: times = [[1,4],[2,3],[4,6]], targetFriend = 1

Step	Friend	Arrival	Leaving	Occupied	Free	Assigned Chair
1	0	1	4	[]	[]	0
2	1	2	3	[(4,0)]	[]	1
3	1 leaves	-	3	[(4,0)]	[1]	-
4	2	4	6	[]	[0,1]