1942. 最小未被占据椅子的编号Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

有 n 个朋友在举办一个派对，这些朋友从 0 到 n - 1 编号。派对里有无数张椅子，编号为 0 到 infinity 。当一个朋友到达派对时，他会占据编号最小且未被占据的椅子。

比方说，当一个朋友到达时，如果椅子 0 ，1 和 5 被占据了，那么他会占据 2 号椅子。当一个朋友离开派对时，他的椅子会立刻变成未占据状态。如果同一时刻有另一个朋友到达，可以立即占据这张椅子。

给你一个下标从 0 开始的二维整数数组 times ，其中 times[i] = [arrivali, leavingi] 表示第 i 个朋友到达和离开的时刻，同时给你一个整数 targetFriend 。所有到达时间互不相同。

请你返回编号为 targetFriend 的朋友占据的椅子编号。

示例 1：

输入：times = [[1,4],[2,3],[4,6]], targetFriend = 1
输出：1
解释：
- 朋友 0 时刻 1 到达，占据椅子 0 。
- 朋友 1 时刻 2 到达，占据椅子 1 。
- 朋友 1 时刻 3 离开，椅子 1 变成未占据。
- 朋友 0 时刻 4 离开，椅子 0 变成未占据。
- 朋友 2 时刻 4 到达，占据椅子 0 。
  朋友 1 占据椅子 1 ，所以返回 1 。

示例 2：

输入：times = [[3,10],[1,5],[2,6]], targetFriend = 0
输出：2
解释：
- 朋友 1 时刻 1 到达，占据椅子 0 。
- 朋友 2 时刻 2 到达，占据椅子 1 。
- 朋友 0 时刻 3 到达，占据椅子 2 。
- 朋友 1 时刻 5 离开，椅子 0 变成未占据。
- 朋友 2 时刻 6 离开，椅子 1 变成未占据。
- 朋友 0 时刻 10 离开，椅子 2 变成未占据。
  朋友 0 占据椅子 2 ，所以返回 2 。

提示：

n == times.length
2 <= n <= 10⁴
times[i].length == 2
1 <= arrivali < leavingi <= 10⁵
0 <= targetFriend <= n - 1
每个 arrivali 时刻互不相同。

# 思路

三个堆，一个堆按照到达时间降序，第二个堆按照离开时间降序，第三个堆按照空座位序号降序，然后模拟，当一个人到达时，首先把离开时间大于小于当前到达时间的座位放入空闲座位堆，然后判断空闲座位是否有座位，有就用，没有就用最后一个座位，然后把当前座位加入quite堆

# 解法

import java.util.PriorityQueue;

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
        PriorityQueue<Integer> pos=new PriorityQueue<>();//空闲座位
        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->a[0]-b[0]);//占领座位
        PriorityQueue<int[]> quite=new PriorityQueue<>((a,b)->a[1]-b[1]);//离开座位
        for(int i=0;i<times.length;i++)
        {
            int[] arr=new int[]{times[i][0],times[i][1],i,0};
            pq.offer(arr);
        }
        int p=0,res=-1;
        while(!pq.isEmpty())
        {
            int[] tmp=pq.poll();
            int time=tmp[0];
            while (!quite.isEmpty()&&quite.peek()[1]<=time)
            {
                int[] q=quite.poll();
                pos.offer(q[3]);
            }
            if(!pos.isEmpty())
            {
                int a=pos.poll();
                tmp[3]=a;
                quite.offer(tmp);
            }else
            {
                tmp[3]=p;
                p++;
                quite.offer(tmp);
            }
            if(tmp[2]==targetFriend)
            {
                res=tmp[3];
                break;
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# 总结

分析出几种情况，然后分别对各个情况实现

#Java