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

有 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 <= 104
• times[i].length == 2
• 1 <= arrivali < leavingi <= 105
• 0 <= targetFriend <= n - 1
• 每个 arrivali 时刻 互不相同 。

方法一：最小堆 + 哈希表

思路与算法

对于每一个人，它会在两个时刻影响椅子占据与否的状态：

• 在他到达时，他会选择占据编号最小的未被占据的椅子；

• 在他离开时，他会释放之前占据的椅子。

这两种情况分别对应以下操作：

• 查询当前未被占据的编号最小的椅子，并将该椅子移出未被占据椅子的集合；

• 查询某个人当前占据的椅子编号，并将该椅子加入未被占据的椅子中。

那么，我们需要用一个数据结构来维护未被占据的椅子，且该数据结构需要在较低的时间复杂度内实现「查询并弹出最小值」与「插入元素」操作。我们可以用一个最小堆实现的优先队列来维护，假设堆的大小为 n，那么它可以做到在 O(\log n) 的时间复杂内完成「查询并弹出最小值」与「插入元素」操作。

另外，考虑到每个人到达时都会占据当前未被占据且编号最小的椅子，那么假设总人数为 n，当所有人都落座时，被占据的椅子编号为 [0, n - 1] 内的整数。因此，我们只需要考虑前 n 把椅子即可。

同时，我们还需要用另一个数据结构维护每个人当前占据的椅子。我们可以用哈希表来实现，其中人的编号为哈希表的键，对应的椅子为哈希表的值。这样我们就可以在 O(1) 的时间复杂度下查询到每个人当前占据的椅子。

我们需要将每个人的到达与离开操作按照时间排序以进行模拟。为了方便模拟，除了上文提及的两个数据结构外，我们可以用 arrival 与 leaving 两个数组分别记录每个人的到达与离开操作，数组的每个元素由操作时间和对应人的编号组成。同时，我们还需要将这两个数组按照时间升序排序。

在模拟之前，最小堆内应包含 [0, n - 1] 内的所有整数，以代表所有椅子都未被占据。模拟过程中，由于涉及到两个数组，我们可以使用双指针的方法保证模拟的时序：遍历排序后的 arrival 数组，并用另一个指针相应地遍历 leaving 数组。每当一个人新到达时，我们需要移动 leaving 数组对应的指针，使得在到达时间及之前的离开操作都被处理。处理离开操作时，我们通过哈希表查询到操作执行人对应的椅子，并将其加入未被占据椅子的最小堆。随后，我们再处理到达操作，首先从最小堆中查询并弹出最小值，同时将人和椅子的键值对放入哈希表中。随后我们判断操作执行人是否为目标，如果是，则返回对应的椅子作为答案。

最后注意到每个人只会到达和离开一次，因此我们不需要在每个人离开时删除哈希表中对应的键值对。

代码

[sol1-C++]

class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        int n = times.size();
        vector<pair<int, int>> arrival;   // 到达操作的时刻和对应的人
        vector<pair<int, int>> leaving;   // 离开操作的时刻和对应的人
        for (int i = 0; i < n; ++i){
            arrival.emplace_back(times[i][0], i);
            leaving.emplace_back(times[i][1], i);
        }
        // 将到达与离开操作按照时间升序排序以方便模拟
        sort(arrival.begin(), arrival.end());
        sort(leaving.begin(), leaving.end());
        priority_queue<int, vector<int>, greater<int>> available;   // 未被占据的椅子
        for (int i = 0; i < n; ++i){
            available.push(i);
        }
        unordered_map<int, int> seats;   // 每个人占据的椅子
        // 双指针模拟
        int j = 0;
        for (auto&& [time, person] : arrival){
            // 处理到达时间与之前的离开操作
            // 将释放的椅子加入未被占据椅子中
            while (j < n && leaving[j].first <= time){
                available.push(seats[leaving[j].second]);
                ++j;
            }
            // 处理到达操作
            // 占据当前编号最小且未被占据的椅子
            int seat = available.top();
            seats[person] = seat;
            available.pop();
            if (person == targetFriend){
                // 如果当前人为目标，则返回对应的椅子
                return seat;
            }
        }
        return -1;
    }
};

[sol1-Python3]

from heapq import heappop, heappush

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        n = len(times)
        arrival = []   # 到达操作的时刻和对应的人
        leaving = []   # 离开操作的时刻和对应的人
        for i in range(n):
            arrival.append((times[i][0], i))
            leaving.append((times[i][1], i))
        # 将到达与离开操作按照时间升序排序以方便模拟
        arrival.sort()
        leaving.sort()
        available = list(range(n))   # 未被占据的椅子
        seats = {}   # 每个人占据的椅子
        # 双指针模拟
        j = 0
        for time, person in arrival:
            # 处理到达时间与之前的离开操作
            # 将释放的椅子加入未被占据椅子中
            while j < n and leaving[j][0] <= time:
                heappush(available, seats[leaving[j][1]])
                j += 1
            # 处理到达操作
            # 占据当前编号最小且未被占据的椅子
            seat = heappop(available)
            seats[person] = seat
            if person == targetFriend:
                # 如果当前人为目标，则返回对应的椅子
                return seat
        return -1

复杂度分析

• 时间复杂度：O(n\log n)，其中 n 为 times 的长度。其中，预处理数据结构的时间复杂度为 O(n\log n)，单次处理到达操作与离开操作的时间复杂度均为 O(\log n)，而我们最多会处理 n 次到达与离开操作。

• 空间复杂度：O(n)。两个数组、最小堆、哈希表的空间开销均为 O(n)。