import heapq

class Solution:
    def smallestChair(self, times, targetFriend):
        n = len(times)
        arrivals = []
        for i, (arr, leave) in enumerate(times):
            arrivals.append((arr, i, leave))
        arrivals.sort()  # Sort by arrival time

        occupied = []  # Min-heap of (leave_time, chair_number)
        free_chairs = []  # Min-heap of available chair numbers
        next_chair = 0  # Next new chair to use

        for arr_time, friend, leave_time in arrivals:
            # Free up chairs for friends who have already left
            while occupied and occupied[0][0] <= arr_time:
                left_time, chair_num = heapq.heappop(occupied)
                heapq.heappush(free_chairs, chair_num)
            # Assign the smallest available chair
            if free_chairs:
                chair = heapq.heappop(free_chairs)
            else:
                chair = next_chair
                next_chair += 1
            heapq.heappush(occupied, (leave_time, chair))
            if friend == targetFriend:
                return chair
    

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

class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        int n = times.size();
        vector<tuple<int, int, int>> arrivals;
        for (int i = 0; i < n; ++i) {
            arrivals.emplace_back(times[i][0], i, times[i][1]);
        }
        sort(arrivals.begin(), arrivals.end());

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> occupied;
        priority_queue<int, vector<int>, greater<int>> freeChairs;
        int nextChair = 0;

        for (auto& [arr, friendIdx, leave] : arrivals) {
            while (!occupied.empty() && occupied.top().first <= arr) {
                freeChairs.push(occupied.top().second);
                occupied.pop();
            }
            int chair;
            if (!freeChairs.empty()) {
                chair = freeChairs.top();
                freeChairs.pop();
            } else {
                chair = nextChair++;
            }
            occupied.push({leave, chair});
            if (friendIdx == targetFriend)
                return chair;
        }
        return -1;
    }
};
    

import java.util.*;

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int n = times.length;
        List<int[]> arrivals = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arrivals.add(new int[]{times[i][0], i, times[i][1]});
        }
        arrivals.sort(Comparator.comparingInt(a -> a[0]));

        PriorityQueue<int[]> occupied = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> freeChairs = new PriorityQueue<>();
        int nextChair = 0;

        for (int[] arr : arrivals) {
            int arrTime = arr[0], friendIdx = arr[1], leaveTime = arr[2];
            while (!occupied.isEmpty() && occupied.peek()[0] <= arrTime) {
                freeChairs.offer(occupied.poll()[1]);
            }
            int chair;
            if (!freeChairs.isEmpty()) {
                chair = freeChairs.poll();
            } else {
                chair = nextChair++;
            }
            occupied.offer(new int[]{leaveTime, chair});
            if (friendIdx == targetFriend)
                return chair;
        }
        return -1;
    }
}
    

class MinHeap {
    constructor(compare) {
        this.data = [];
        this.compare = compare;
    }
    push(item) {
        this.data.push(item);
        this._siftUp();
    }
    pop() {
        if (this.data.length === 1) return this.data.pop();
        const top = this.data[0];
        this.data[0] = this.data.pop();
        this._siftDown();
        return top;
    }
    peek() {
        return this.data[0];
    }
    size() {
        return this.data.length;
    }
    _siftUp() {
        let i = this.data.length - 1;
        while (i > 0) {
            let p = Math.floor((i - 1) / 2);
            if (this.compare(this.data[i], this.data[p]) < 0) {
                [this.data[i], this.data[p]] = [this.data[p], this.data[i]];
                i = p;
            } else break;
        }
    }
    _siftDown() {
        let i = 0;
        const n = this.data.length;
        while (true) {
            let l = 2 * i + 1, r = 2 * i + 2, smallest = i;
            if (l < n && this.compare(this.data[l], this.data[smallest]) < 0) smallest = l;
            if (r < n && this.compare(this.data[r], this.data[smallest]) < 0) smallest = r;
            if (smallest === i) break;
            [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
            i = smallest;
        }
    }
}

var smallestChair = function(times, targetFriend) {
    let arrivals = times.map((time, i) => [time[0], i, time[1]]);
    arrivals.sort((a, b) => a[0] - b[0]);
    let occupied = new MinHeap((a, b) => a[0] - b[0]);
    let freeChairs = new MinHeap((a, b) => a - b);
    let nextChair = 0;

    for (let [arrTime, friend, leaveTime] of arrivals) {
        while (occupied.size() > 0 && occupied.peek()[0] <= arrTime) {
            freeChairs.push(occupied.pop()[1]);
        }
        let chair;
        if (freeChairs.size() > 0) {
            chair = freeChairs.pop();
        } else {
            chair = nextChair++;
        }
        occupied.push([leaveTime, chair]);
        if (friend === targetFriend) return chair;
    }
    return -1;
};