Medium

题目描述

有一场聚会，n 个朋友编号从 0 到 n - 1。聚会上有无限个椅子，编号从 0 到无穷大。当一个朋友到达聚会时，他们会坐在编号最小的未被占据的椅子上。

例如，如果椅子 0、1 和 5 被占据，当一个朋友来时，他们会坐在椅子编号 2 上。

当一个朋友离开聚会时，他们的椅子在离开的那一刻变为未被占据。如果另一个朋友在同一时刻到达，他们可以坐在那个椅子上。

给你一个下标从 0 开始的二维整数数组 times，其中 times[i] = [arrival_i, leaving_i] 表示第 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^4
  • times[i].length == 2
  • 1 <= arrival_i < leaving_i <= 10^5
  • 0 <= targetFriend <= n - 1
  • 每个 arrival_i 时间都是不同的。

解题思路

这是一道模拟题，需要处理椅子的分配和释放过程。核心思路是使用两个优先队列来管理椅子状态。

解题思路：

  1. 事件驱动模拟：将所有朋友的到达和离开看作事件，按时间顺序处理
  2. 椅子管理：使用最小堆维护可用椅子编号，确保总是分配最小编号的椅子
  3. 离开事件处理：使用另一个最小堆记录离开事件，当到达某个时间点时，先处理所有在该时间点离开的朋友

具体步骤：

  • 创建一个包含朋友编号的事件数组，按到达时间排序
  • 使用 availableChairs 最小堆维护可用椅子编号
  • 使用 leavingQueue 最小堆维护离开事件 (离开时间, 椅子编号)
  • 对每个到达事件：
    1. 先处理当前时间的所有离开事件，释放椅子
    2. 分配最小可用椅子给当前朋友
    3. 如果是目标朋友，返回椅子编号

时间复杂度优化： 通过优先队列，椅子分配和释放都是 O(log n) 操作，总体效率较高。

代码实现

class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        vector<pair<int, int>> events; // {arrival_time, friend_id}
        for (int i = 0; i < times.size(); i++) {
            events.push_back({times[i][0], i});
        }
        sort(events.begin(), events.end());
        
        priority_queue<int, vector<int>, greater<int>> availableChairs; // min heap
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> leavingQueue; // {leave_time, chair}
        
        // Initialize available chairs
        for (int i = 0; i < times.size(); i++) {
            availableChairs.push(i);
        }
        
        for (auto& event : events) {
            int arrivalTime = event.first;
            int friendId = event.second;
            
            // Process all friends leaving at or before current arrival time
            while (!leavingQueue.empty() && leavingQueue.top().first <= arrivalTime) {
                availableChairs.push(leavingQueue.top().second);
                leavingQueue.pop();
            }
            
            // Assign chair to current friend
            int chair = availableChairs.top();
            availableChairs.pop();
            
            if (friendId == targetFriend) {
                return chair;
            }
            
            // Add leaving event for this friend
            leavingQueue.push({times[friendId][1], chair});
        }
        
        return -1;
    }
};

class Solution:
    def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
        import heapq
        
        events = [(times[i][0], i) for i in range(len(times))]
        events.sort()
        
        available_chairs = list(range(len(times)))  # min heap
        heapq.heapify(available_chairs)
        leaving_queue = []  # (leave_time, chair)
        
        for arrival_time, friend_id in events:
            # Process all friends leaving at or before current arrival time
            while leaving_queue and leaving_queue[0][0] <= arrival_time:
                _, chair = heapq.heappop(leaving_queue)
                heapq.heappush(available_chairs, chair)
            
            # Assign chair to current friend
            chair = heapq.heappop(available_chairs)
            
            if friend_id == targetFriend:
                return chair
            
            # Add leaving event for this friend
            heapq.heappush(leaving_queue, (times[friend_id][1], chair))
        
        return -1

public class Solution {
    public int SmallestChair(int[][] times, int targetFriend) {
        var events = new List<(int arrival, int friendId)>();
        for (int i = 0; i < times.Length; i++) {
            events.Add((times[i][0], i));
        }
        events.Sort();
        
        var availableChairs = new PriorityQueue<int, int>();
        var leavingQueue = new PriorityQueue<(int leaveTime, int chair), int>();
        
        // Initialize available chairs
        for (int i = 0; i < times.Length; i++) {
            availableChairs.Enqueue(i, i);
        }
        
        foreach (var (arrivalTime, friendId) in events) {
            // Process all friends leaving at or before current arrival time
            while (leavingQueue.Count > 0 && leavingQueue.Peek().leaveTime <= arrivalTime) {
                var (_, chair) = leavingQueue.Dequeue();
                availableChairs.Enqueue(chair, chair);
            }
            
            // Assign chair to current friend
            int assignedChair = availableChairs.Dequeue();
            
            if (friendId == targetFriend) {
                return assignedChair;
            }
            
            // Add leaving event for this friend
            leavingQueue.Enqueue((times[friendId][1], assignedChair), times[friendId][1]);
        }
        
        return -1;
    }
}

var smallestChair = function(times, targetFriend) {
    const events = [];
    
    for (let i = 0; i < times.length; i++) {
        events.push([times[i][0], i, 'arrive']);
        events.push([times[i][1], i, 'leave']);
    }
    
    events.sort((a, b) => {
        if (a[0] === b[0]) {
            return a[2] === 'leave' ? -1 : 1;
        }
        return a[0] - b[0];
    });
    
    const availableChairs = [];
    const occupiedChairs = new Map();
    let nextChair = 0;
    
    for (const [time, friend, action] of events) {
        if (action === 'leave') {
            const chair = occupiedChairs.get(friend);
            occupiedChairs.delete(friend);
            availableChairs.push(chair);
            availableChairs.sort((a, b) => a - b);
        } else {
            let chair;
            if (availableChairs.length > 0) {
                chair = availableChairs.shift();
            } else {
                chair = nextChair++;
            }
            
            occupiedChairs.set(friend, chair);
            
            if (friend === targetFriend) {
                return chair;
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序事件需要 O(n log n)，每次椅子分配和释放操作需要 O(log n)，总共 n 次操作
空间复杂度O(n)需要存储事件列表、可用椅子堆和离开事件堆，都是 O(n) 空间