The Number of the Smallest Unoccupied Chair solution and explanation

import heapq

def smallestChair(times, targetFriend):
    events = []
    for i, (arr, leave) in enumerate(times):
        events.append((arr, i, 'arrive'))
        events.append((leave, i, 'leave'))
    events.sort()
    
    available_chairs = []  # Min-heap for available chair numbers
    occupied_map = {}  # Maps friends to chairs
    current_chair = 0
    
    for time, friend, event_type in events:
        if event_type == 'arrive':
            if not available_chairs:
                chair = current_chair
                current_chair += 1
            else:
                chair = heapq.heappop(available_chairs)
            
            occupied_map[friend] = chair
            
            if friend == targetFriend:
                return chair
        else:  # event_type == 'leave'
            heapq.heappush(available_chairs, occupied_map[friend])

function smallestChair(times, targetFriend) {
    let events = [];
    times.forEach(([arrival, leave], index) => {
        events.push({ time: arrival, index, type: 'arrive' });
        events.push({ time: leave, index, type: 'leave' });
    });
    events.sort((a, b) => a.time - b.time || (a.type === 'leave' ? -1 : 1));

    let availableChairs = new MinPriorityQueue();
    let occupiedChairs = new Map();
    let currentChair = 0;

    for (const { time, index, type } of events) {
        if (type === 'arrive') {
            let chair = availableChairs.isEmpty() ? currentChair++ : availableChairs.dequeue().element;
            occupiedChairs.set(index, chair);

            if (index === targetFriend) {
                return chair;
            }
        } else {
            availableChairs.enqueue(occupiedChairs.get(index));
        }
    }
}

import java.util.*;

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        List<int[]> events = new ArrayList<>();
        for (int i = 0; i < times.length; i++) {
            events.add(new int[]{times[i][0], i, 1});  // 1 for arrival
            events.add(new int[]{times[i][1], i, -1}); // -1 for departure
        }
        events.sort((a, b) -> a[0] == b[0] ? Integer.compare(a[2], b[2]) : Integer.compare(a[0], b[0]));

        TreeSet<Integer> availableChairs = new TreeSet<>();
        Map<Integer, Integer> friendToChair = new HashMap<>();
        int nextChair = 0;

        for (int[] event : events) {
            if (event[2] == 1) {  // Arrival
                int chair;
                if (!availableChairs.isEmpty()) {
                    chair = availableChairs.pollFirst();
                } else {
                    chair = nextChair++;
                }
                friendToChair.put(event[1], chair);
                if (event[1] == targetFriend) {
                    return chair;
                }
            } else {  // Departure
                availableChairs.add(friendToChair.get(event[1]));
            }
        }
        return -1;
    }
}

#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int smallestChair(vector<vector<int>>& times, int targetFriend) {
    vector<pair<int, int>> events;
    for (int i = 0; i < times.size(); ++i) {
        events.emplace_back(times[i][0], i);
        events.emplace_back(times[i][1], -i);
    }
    sort(events.begin(), events.end());

    set<int> available_chairs;
    vector<int> friend_to_chair(times.size(), -1);
    int next_chair = 0;

    for (const auto& event : events) {
        int time = event.first;
        int index = event.second;

        if (index >= 0) {  // Arrival event
            int chairNumber;
            if (!available_chairs.empty()) {
                chairNumber = *available_chairs.begin();
                available_chairs.erase(available_chairs.begin());
            } else {
                chairNumber = next_chair++;
            }
            friend_to_chair[index] = chairNumber;

            if (index == targetFriend)
                return chairNumber;

        } else {  // Departure event
            int leavingFriend = -index;
            available_chairs.insert(friend_to_chair[leavingFriend]);
        }
    }
    return -1;
}

function smallestChair(times: number[][], targetFriend: number): number {
    const n = times.length;
    const idle = new MinPriorityQueue<number>();
    const busy = new PriorityQueue((a, b) => a[0] - b[0]);
    for (let i = 0; i < n; ++i) {
        times[i].push(i);
        idle.enqueue(i);
    }
    times.sort((a, b) => a[0] - b[0]);
    for (const [arrival, leaving, i] of times) {
        while (busy.size() > 0 && busy.front()[0] <= arrival) {
            idle.enqueue(busy.dequeue()[1]);
        }
        const j = idle.dequeue();
        if (i === targetFriend) {
            return j;
        }
        busy.enqueue([leaving, j]);
    }
    return -1;
}

func smallestChair(times [][]int, targetFriend int) int {
	idle := hp{}
	busy := hp2{}
	for i := range times {
		times[i] = append(times[i], i)
		heap.Push(&idle, i)
	}
	sort.Slice(times, func(i, j int) bool { return times[i][0] < times[j][0] })
	for _, e := range times {
		arrival, leaving, i := e[0], e[1], e[2]
		for len(busy) > 0 && busy[0].t <= arrival {
			heap.Push(&idle, heap.Pop(&busy).(pair).i)
		}
		j := heap.Pop(&idle).(int)
		if i == targetFriend {
			return j
		}
		heap.Push(&busy, pair{leaving, j})
	}
	return -1
}

type hp struct{ sort.IntSlice }

func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any)        { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
	a := h.IntSlice
	v := a[len(a)-1]
	h.IntSlice = a[:len(a)-1]
	return v
}

type pair struct{ t, i int }
type hp2 []pair

func (h hp2) Len() int           { return len(h) }
func (h hp2) Less(i, j int) bool { return h[i].t < h[j].t || (h[i].t == h[j].t && h[i].i < h[j].i) }
func (h hp2) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }