LeetCode——5805. 最小未被占據椅子的編號[The Number of the Smallest Unoccupied Chair][中等]——分析及代碼[Java]

• 一、題目
• 二、分析及代碼
• • 1. 堆（優(yōu)先隊列）
  • • （1）思路
    • （2）代碼
    • （3）結果
• 三、其他

一、題目

有 n 個朋友在舉辦一個派對，這些朋友從 0 到 n - 1 編號。派對里有 無數 張椅子，編號為 0 到 infinity 。當一個朋友到達派對時，他會占據 編號最小 且未被占據的椅子。

• 比方說，當一個朋友到達時，如果椅子 0 ，1 和 5 被占據了，那么他會占據 2 號椅子。

當一個朋友離開派對時，他的椅子會立刻變成未占據狀態(tài)。如果同一時刻有另一個朋友到達，可以立即占據這張椅子。

給你一個下標從 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^4
• times[i].length == 2
• 1 <= arrivali < leavingi <= 10^5
• 0 <= targetFriend <= n - 1
• 每個?arrivali?時刻?互不相同?。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/the-number-of-the-smallest-unoccupied-chair
著作權歸領扣網絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

二、分析及代碼

1. 堆（優(yōu)先隊列）

（1）思路

設計 3 個小頂堆，分別存放到達、離開的時間及對應朋友的編號，和可使用的椅子編號，然后模擬朋友們的來訪過程，直至目標朋友到達。

（2）代碼

class Solution {public int smallestChair(int[][] times, int targetFriend) {int n = times.length, targetTime = times[targetFriend][0];//朋友數量，目標時間，即目標朋友到達的時間PriorityQueue<int[]> arrTime = new PriorityQueue<>((a1, a2) -> a1[0] - a2[0]);//小頂堆，按到達的順序存放對應時間及朋友編號PriorityQueue<int[]> leaTime = new PriorityQueue<>((l1, l2) -> l1[0] - l2[0]);//小頂堆，按離開的順序存放對應時間及朋友編號for (int i = 0; i < n; i++) {if (times[i][0] <= targetTime)//不晚于目標時間的到達時刻及對應編號入堆arrTime.offer(new int[]{times[i][0], i});if (times[i][1] <= targetTime)//不晚于目標時間的離開時刻及對應編號入堆leaTime.offer(new int[]{times[i][1], i});}PriorityQueue<Integer> chair = new PriorityQueue<Integer>();//小頂堆，存放可用椅子編號for (int i = 0; i < n; i++)//初始化，n個朋友最多使用n個椅子chair.offer(i);int[] usedChair = new int[n];//各位朋友使用的椅子編號int t = arrTime.peek()[0];//當前時刻while (t < targetTime) {//模擬usedChair[arrTime.poll()[1]] = chair.poll();//當前到達的朋友使用椅子t = arrTime.peek()[0];//時間跳轉到下一朋友到達while (!leaTime.isEmpty() && leaTime.peek()[0] <= t)//之前的朋友歸還椅子chair.offer(usedChair[leaTime.poll()[1]]);}return chair.poll();//目標朋友到達，輸出當前的最小椅子} }

（3）結果

執(zhí)行用時 ：51 ms，在所有 Java 提交中擊敗了 100.00% 的用戶；
內存消耗 ：46.4 MB，在所有 Java 提交中擊敗了 100.00% 的用戶。
（目前提交用戶量不足，暫無排名）

三、其他

暫無。

總結

以上是生活随笔為你收集整理的LeetCode——5805. 最小未被占据椅子的编号(The Number of the Smallest Unoccupied Chair)[中等]——分析及代码（Java）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。