The Number of the Smallest Unoccupied Chair

medium heap sorting simulation

Problem

There is an unlimited row of chairs numbered 0, 1, 2, … (all initially empty). You are given times[i] = [arrival, leaving] for friend i, where every arrival time is distinct. When a friend arrives they immediately sit in the smallest-numbered chair that is currently free; the moment a friend leaves, their chair becomes free again and can be reused at that same instant by anyone arriving then. Given an integer targetFriend, return the number of the chair that friend targetFriend ends up sitting in.

Inputtimes = [[3,10],[1,5],[2,6]], targetFriend = 0

Output2

Friend 1 arrives at t=1 → chair 0. Friend 2 arrives at t=2 → chair 1. Friend 0 arrives at t=3; chairs 0 and 1 are still taken, so friend 0 takes chair 2.

times (arrival:leaving, comma-separated)

targetFriend

import heapq

def smallest_chair(times, target_friend):
    target = times[target_friend][0]
    people = sorted(range(len(times)), key=lambda i: times[i][0])
    free = list(range(len(times)))      # min-heap of free chair numbers
    occupied = []                       # min-heap of (leave_time, chair)
    for i in people:
        arrive, leave = times[i]
        while occupied and occupied[0][0] <= arrive:
            heapq.heappush(free, heapq.heappop(occupied)[1])
        chair = heapq.heappop(free)
        if arrive == target:
            return chair
        heapq.heappush(occupied, (leave, chair))
    return -1

function smallestChair(times, targetFriend) {
  const target = times[targetFriend][0];
  const people = times.map((_, i) => i)
    .sort((a, b) => times[a][0] - times[b][0]);
  const free = times.map((_, i) => i);       // min-heap of chairs
  const occupied = [];                        // [leave, chair], min by leave
  for (const i of people) {
    const [arrive, leave] = times[i];
    while (occupied.length && occupied[0][0] <= arrive)
      free.push(occupied.shift()[1]);
    free.sort((a, b) => a - b);
    const chair = free.shift();
    if (arrive === target) return chair;
    occupied.push([leave, chair]);
    occupied.sort((a, b) => a[0] - b[0]);
  }
  return -1;
}

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int target = times[targetFriend][0];
        Integer[] people = new Integer[times.length];
        for (int i = 0; i < times.length; i++) people[i] = i;
        Arrays.sort(people, (a, b) -> times[a][0] - times[b][0]);
        PriorityQueue<Integer> free = new PriorityQueue<>();
        for (int i = 0; i < times.length; i++) free.offer(i);
        PriorityQueue<int[]> occupied =
            new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i : people) {
            int arrive = times[i][0], leave = times[i][1];
            while (!occupied.isEmpty() && occupied.peek()[0] <= arrive)
                free.offer(occupied.poll()[1]);
            int chair = free.poll();
            if (arrive == target) return chair;
            occupied.offer(new int[]{leave, chair});
        }
        return -1;
    }
}

int smallestChair(vector<vector<int>>& times, int targetFriend) {
    int target = times[targetFriend][0];
    vector<int> people(times.size());
    iota(people.begin(), people.end(), 0);
    sort(people.begin(), people.end(),
         [&](int a, int b) { return times[a][0] < times[b][0]; });
    priority_queue<int, vector<int>, greater<>> freeChairs;
    for (int i = 0; i < (int)times.size(); i++) freeChairs.push(i);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> occupied;
    for (int i : people) {
        int arrive = times[i][0], leave = times[i][1];
        while (!occupied.empty() && occupied.top().first <= arrive) {
            freeChairs.push(occupied.top().second); occupied.pop();
        }
        int chair = freeChairs.top(); freeChairs.pop();
        if (arrive == target) return chair;
        occupied.push({leave, chair});
    }
    return -1;
}

Explanation

The seating rule has two moving parts: a friend always grabs the smallest-numbered free chair, and a chair only becomes reusable after its current occupant's leaving time. Both "smallest" lookups are exactly what a min-heap gives in O(log n), so we keep two heaps: one of free chair numbers, and one of currently occupied seats keyed by leave time.

Because friends do not act in input order but in arrival order, we first sort the friend indices by arrival time (all arrivals are distinct, so there are no ties to worry about). We also stash the target friend's arrival time up front, since that single timestamp is all we need to recognize the moment we care about.

Now we process arrivals one by one. Before seating the incoming friend, we release every chair whose occupant has already left (leave time ≤ this arrival) by popping it from the occupied heap and pushing its number back onto the free heap. Then we pop the smallest free chair and seat the friend there. If this friend is the target, that chair number is the answer and we stop. Otherwise we record the seat in the occupied heap with its leave time and move on.

Walking the example times = [[3,10],[1,5],[2,6]], targetFriend = 0 (so target arrival = 3): friend 1 arrives at t=1 and takes chair 0; friend 2 arrives at t=2 and takes chair 1; friend 0 arrives at t=3, but nobody has left yet (earliest leave is 5), so the free heap still starts at chair 2 — friend 0 sits in chair 2.

The dominant cost is the initial sort and the heap operations: each of the n friends is pushed and popped from the occupied heap at most once. That gives O(n log n) time and O(n) space for the two heaps and the sorted order. Using leave times as the heap key is what lets us free seats lazily instead of scanning a clock tick by tick.

Time: O(n log n) Space: O(n)