There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.


	For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.


When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.

Return the chair number that the friend numbered targetFriend will sit on.

&nbsp;
Example 1:

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: 
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.


Example 2:

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: 
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.


&nbsp;
Constraints:


	n == times.length
	2 &lt;= n &lt;= 104
	times[i].length == 2
	1 &lt;= arrivali &lt; leavingi &lt;= 105
	0 &lt;= targetFriend &lt;= n - 1
	Each arrivali time is distinct.


class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        arrivals = []
        departures = []
        for ind, (x, y) in enumerate(times):
            heappush(arrivals, (x, ind))
            heappush(departures, (y, ind))
        d = {}
        occupied = [0] * len(times)
        while True:
            if arrivals and departures and arrivals[0][0] < departures[0][0]:
                _, ind = heappop(arrivals)
                d[ind] = occupied.index(0)
                occupied[d[ind]] = 1
                if ind == targetFriend:
                    return d[ind]
            elif arrivals and departures and arrivals[0][0] >= departures[0][0]:
                _, ind = heappop(departures)
                occupied[d[ind]] = 0
class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int targetStart = times[targetFriend][0];
        Arrays.sort(times, (a, b) -> a[0] - b[0]);

        PriorityQueue<Integer> available = new PriorityQueue<>();
        for (int i = 0; i < times.length; ++ i) {
            available.offer(i);
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        for (int i = 0; i < times.length; ++ i) {
            while (!pq.isEmpty() && pq.peek()[0] <= times[i][0]) {
                available.offer(pq.poll()[1]);
            }

            if (times[i][0] == targetStart) {
                break;
            }

            pq.offer(new int[]{times[i][1], available.poll()});
        }

        return available.peek();
    }
}
class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        
        int n = times.size();
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > busy; //departure time as first , index as second
        priority_queue<int, vector<int>, greater<int>> free; //min heap of chair index that are unoccupied
        
		//store friend indexes so that they don't get lost after sorting
        for(int i=0;i<n;++i){
            times[i].push_back(i);
        }
		//Sort according to arrival time
        sort(times.begin(),times.end());
        
		int new_chair = 0; //chairs alloted till now 
        for(int i=0;i<n;++i){
            int arrival = times[i][0]; //pop chairs before arrival 
            int leave_time = times[i][1];
            int fr = times[i][2]; //friend index
            //free chairs accordingly
            while(!busy.empty() && busy.top().first <= arrival){
                // cout << "Chair free " << busy.top().second << endl;
                free.push(busy.top().second);
                busy.pop();
            }   
            //No free chair allot new chair
            if(free.empty()){
                // cout << "Alloting new_chair " << new_chair << "to" << fr << endl;
                if(fr  == targetFriend) return new_chair;
                busy.push({leave_time,new_chair});
                new_chair++;
            }
            else{
                int x = free.top();
                // cout << "giving chair " << x << "to" << fr << endl;
                free.pop();
                if( fr  == targetFriend) return x; 
                busy.push({leave_time,x});
            }
        }
        return -1;
    }
    
};
/**
 * @param {number[][]} times
 * @param {number} targetFriend
 * @return {number}
 */
var smallestChair = function(times, targetFriend) {
    const [targetArrival] = times[targetFriend]; // we need only arrival time
    const arrivalQueue = times;
    const leavingQueue = [...times];
    arrivalQueue.sort((a, b) => a[0] - b[0]); // sort by arrival time
    leavingQueue.sort((a, b) => (a[1] - b[1]) || (a[0] - b[0])); // sort by leaving time and if they are equal by arrival
    const chairsByLeaveTime = new Map(); // key - arrival time, value - chair index
    let chairsCount = 0;
    let arriving = 0, leaving = 0; // two pointers for keeping track of available chairs

    while (arriving < arrivalQueue.length) {
        let chairIdx;
        const arrival = arrivalQueue[arriving][0];
        const leave = leavingQueue[leaving][1];
        if (arrival < leave) {
            chairIdx = chairsCount++; // if no one is leaving, take a new chair
        } else {
            let freeChairIdx = leaving;
            chairIdx = chairsByLeaveTime.get(leavingQueue[freeChairIdx++][0]); // when arriaval time is less then or equal to the next leaving friend we can take her chair
            while (arrival >= leavingQueue[freeChairIdx][1]) { // to avoid situation when a few friends left already and the next chair in leaving queue is not the smallest
                const nextChair = chairsByLeaveTime.get(leavingQueue[freeChairIdx][0]);
                if (chairIdx > nextChair) {
                    [leavingQueue[leaving], leavingQueue[freeChairIdx]] = [leavingQueue[freeChairIdx], leavingQueue[leaving]]; // swap the front of the queue with the smallest chair owner
                    chairIdx = nextChair;
                }
                ++freeChairIdx;
            }
            ++leaving;
        }
        if (targetArrival === arrival) { // we found the target, no need to continue
            return chairIdx;
        }
        chairsByLeaveTime.set(arrival, chairIdx); // as far as arrival time is distinct, we can use it as a key
        arriving++;
    }
};
The Number of the Smallest Unoccupied Chair