# 1942. The Number of the Smallest Unoccupied Chair
###### tags: `Leetcode` `Medium` `Priority Queue`
Link: https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair/
## 思路 $O(NlogN)$ $O(N)$
availableChairs里面存循环利用的chair
friends里面存一个friend离开的时间和他们占的椅子
然后遍历times，每次先把在当下friend来之前要离开的friend从friends里面拿走，把他们的椅子放在availableChairs里面
然后开始研究当下friend坐在哪个椅子，如果availableChairs里面没有椅子了，那么就只能开新椅子 也就是nextChair++（nextChair是单调递增的），否则就拿availableChairs里面最小的那个
因为每个friend的arrive time都是distinct 因此可以用targetfriend的arrival time判断当下friend是不是targetfriend
## Code

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        int targetFriendTime = times[targetFriend][0];
        Arrays.sort(times, (a,b)->(a[0]-b[0]));
        Queue<Integer> availableChairs = new PriorityQueue<>();
        // 0 time to leave 1 chair
        Queue<int[]> friends = new PriorityQueue<>((a,b)->(a[0]-b[0]));
        int nextChair = 0;
        for(int[] time:times){
            while(!friends.isEmpty() && friends.peek()[0]<=time[0]){
                availableChairs.add(friends.poll()[1]);
            }
            
            int chair;
            if(availableChairs.isEmpty()) chair = nextChair++;
            else chair = availableChairs.poll();
            
            if(targetFriendTime == time[0]) return chair;
            
            friends.add(new int[]{time[1], chair});
        }
        return nextChair;
    }
}