最小未被占据椅子的编号

标签: 数组 哈希表 堆（优先队列）

难度: Medium

有 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 时刻 互不相同 。

Submission

运行时间: 129 ms

内存: 20.4 MB

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        for i, x in enumerate(times):
            times[i] = x + [i]
        times.sort(key=lambda x: x[0])
        leave_times = []
        avail_chairs = list(range(0, len(times)))
        heapify(avail_chairs)
        for arrive_t, leave_t, idx in times:
            while leave_times and leave_times[0][0] <= arrive_t:
                _, pre_chair, _ = heappop(leave_times)
                heappush(avail_chairs, pre_chair)
            chair = heappop(avail_chairs)
            if idx == targetFriend:
                return chair
            heappush(leave_times, (leave_t, chair, idx))

Explain

首先，解题思路是将每个朋友的到达和离开时间转换为一个事件列表，并包含每个朋友的索引。对这个列表根据到达时间进行排序。使用一个最小堆来跟踪当前可用的椅子编号，另一个最小堆来维护离开时间和对应的椅子编号。遍历每个事件，如果有朋友离开（即当前时间大于等于堆顶的离开时间），则将对应的椅子编号放回可用椅子堆中。如果有朋友到达，则从可用椅子堆中取出最小的椅子编号，并记录该朋友使用的椅子。如果当前到达的朋友是目标朋友，直接返回其所使用的椅子编号。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        # 给每个朋友的时间加上索引
        for i, x in enumerate(times):
            times[i] = x + [i]
        # 根据到达时间排序
        times.sort(key=lambda x: x[0])
        # 初始化离开时间堆
        leave_times = []
        # 初始化可用椅子堆，并堆化
        avail_chairs = list(range(0, len(times)))
        heapify(avail_chairs)
        # 遍历每个事件
        for arrive_t, leave_t, idx in times:
            # 处理所有已经离开的朋友，回收椅子
            while leave_times and leave_times[0][0] <= arrive_t:
                _, pre_chair, _ = heappop(leave_times)
                heappush(avail_chairs, pre_chair)
            # 分配椅子给当前到达的朋友
            chair = heappop(avail_chairs)
            # 如果是目标朋友，返回结果
            if idx == targetFriend:
                return chair
            # 将当前朋友的离开事件加入堆中
            heappush(leave_times, (leave_t, chair, idx))

Explore

在题解中，我们使用了一个最小堆来维护离开时间和椅子编号的关系。每个元素是一个元组，包含离开时间、椅子编号和朋友的索引。最小堆的性质确保了堆顶元素总是拥有最小的离开时间。在处理事件时，我们会循环检查堆顶元素的离开时间是否小于或等于当前事件的到达时间。如果是，就将该椅子编号回收至另一个最小堆（可用椅子堆）。由于这个可用椅子堆也是最小堆，它保证了每次从中取出或插入元素都会维持椅子编号的最小序，即每次都可以分配最小的未被占用的椅子编号。因此，即使多个朋友同时离开，我们也能确保椅子编号正确回收，且按照最小编号优先原则进行再分配。

在这个题解中，处理事件的逻辑是基于朋友的到达时间顺序进行的。每个到达事件都在处理完之前所有必要的离开事件之后立即处理。这意味着，只要目标朋友到达时，我们已经处理了所有先前到达且必须在目标朋友之前离开的朋友的离开事件。因此，如果在目标朋友到达之前处理所有事件，实际上我们只处理到目标朋友到达之前的事件。一旦目标朋友到达并被分配了椅子，我们就返回这个椅子编号作为结果，而不需要关心后续的任何事件。这不会影响结果，因为目标朋友的椅子编号一旦确定，即使后续有更多事件发生，也不会影响已经分配给目标朋友的椅子编号。