The Number of the Smallest Unoccupied Chair

class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        int n = times.size();
        vector<tuple<int,int,int>> arrs(n);
        for (int i = 0; i < n; ++i) arrs[i] = {times[i][0], times[i][1], i};
        sort(arrs.begin(), arrs.end());
        priority_queue<int, vector<int>, greater<int>> freeChairs;
        for (int i = 0; i < n; ++i) freeChairs.push(i);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> busy;
        for (auto& [arr, lea, idx] : arrs) {
            while (!busy.empty() && busy.top().first <= arr) {
                freeChairs.push(busy.top().second);
                busy.pop();
            }
            int chair = freeChairs.top(); freeChairs.pop();
            if (idx == targetFriend) return chair;
            busy.push({lea, chair});
        }
        return -1;
    }
};

import (
  "container/heap"
  "sort"
)

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{}   { o := *h; n := len(o); x := o[n-1]; *h = o[:n-1]; return x }

type busyItem struct{ leave, chair int }
type busyHeap []busyItem

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

func smallestChair(times [][]int, targetFriend int) int {
  n := len(times)
  type arr struct{ arrive, leave, idx int }
  arrs := make([]arr, n)
  for i, t := range times {
    arrs[i] = arr{t[0], t[1], i}
  }
  sort.Slice(arrs, func(i, j int) bool { return arrs[i].arrive < arrs[j].arrive })
  free := &intHeap{}
  for i := 0; i < n; i++ {
    heap.Push(free, i)
  }
  busy := &busyHeap{}
  for _, a := range arrs {
    for busy.Len() > 0 && (*busy)[0].leave <= a.arrive {
      b := heap.Pop(busy).(busyItem)
      heap.Push(free, b.chair)
    }
    chair := heap.Pop(free).(int)
    if a.idx == targetFriend {
      return chair
    }
    heap.Push(busy, busyItem{a.leave, chair})
  }
  return -1
}

import heapq
from typing import List

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        n = len(times)
        arrs = sorted([(t[0], t[1], i) for i, t in enumerate(times)])
        free = list(range(n))
        heapq.heapify(free)
        busy: List[tuple] = []
        for arrive, leave, idx in arrs:
            while busy and busy[0][0] <= arrive:
                _, chair = heapq.heappop(busy)
                heapq.heappush(free, chair)
            chair = heapq.heappop(free)
            if idx == targetFriend:
                return chair
            heapq.heappush(busy, (leave, chair))
        return -1

class MinHeap {
    constructor(cmp) { this.h = []; this.cmp = cmp; }
    size() { return this.h.length; }
    top() { return this.h[0]; }
    push(x) {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[p], this.h[i]) <= 0) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                let l = i * 2 + 1, r = i * 2 + 2, s = i;
                if (l < n && this.cmp(this.h[l], this.h[s]) < 0) s = l;
                if (r < n && this.cmp(this.h[r], this.h[s]) < 0) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

var smallestChair = function(times, targetFriend) {
    const n = times.length;
    const arrs = times.map((t, i) => [t[0], t[1], i]);
    arrs.sort((a, b) => a[0] - b[0]);
    const free = new MinHeap((a, b) => a - b);
    for (let i = 0; i < n; i++) free.push(i);
    const busy = new MinHeap((a, b) => a[0] - b[0]);
    for (const [arrive, leave, idx] of arrs) {
        while (busy.size() && busy.top()[0] <= arrive) {
            const [, chair] = busy.pop();
            free.push(chair);
        }
        const chair = free.pop();
        if (idx === targetFriend) return chair;
        busy.push([leave, chair]);
    }
    return -1;
};

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

class MinHeap<T> {
    h: T[] = [];
    cmp: (a: T, b: T) => number;
    constructor(cmp: (a: T, b: T) => number) { this.cmp = cmp; }
    size(): number { return this.h.length; }
    top(): T { return this.h[0]; }
    push(x: T): void {
        this.h.push(x);
        let i: number = this.h.length - 1;
        while (i > 0) {
            const p: number = (i - 1) >> 1;
            if (this.cmp(this.h[p], this.h[i]) <= 0) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): T {
        const top: T = this.h[0];
        const last: T = this.h.pop() as T;
        if (this.h.length) {
            this.h[0] = last;
            let i: number = 0;
            const n: number = this.h.length;
            while (true) {
                let l: number = i * 2 + 1, r: number = i * 2 + 2, s: number = i;
                if (l < n && this.cmp(this.h[l], this.h[s]) < 0) s = l;
                if (r < n && this.cmp(this.h[r], this.h[s]) < 0) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function smallestChair(times: number[][], targetFriend: number): number {
    const n: number = times.length;
    const arrs: number[][] = times.map((t: number[], i: number) => [t[0], t[1], i]);
    arrs.sort((a: number[], b: number[]) => a[0] - b[0]);
    const free: MinHeap<number> = new MinHeap<number>((a: number, b: number) => a - b);
    for (let i = 0; i < n; i++) free.push(i);
    const busy: MinHeap<number[]> = new MinHeap<number[]>((a: number[], b: number[]) => a[0] - b[0]);
    for (const [arrive, leave, idx] of arrs) {
        while (busy.size() && busy.top()[0] <= arrive) {
            const [, chair] = busy.pop();
            free.push(chair);
        }
        const chair: number = free.pop();
        if (idx === targetFriend) return chair;
        busy.push([leave, chair]);
    }
    return -1;
}