有 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.length2 n 104^44times[i].length 21 arrivali leavingi 105^550 targetFriend n - 1每个 arrivali 时刻 互不相同 。我们可以用一个变量来记录已经分配的椅子的最大编号然后用一个小顶堆来管理曾分配出去但又释放掉的椅子到达时刻和离开时刻也可以用小顶堆来管理classSolution{public:intsmallestChair(vectorvectorinttimes,inttargetFriend){vectorpairint,intarrivalTime(times.size());for(inti0;itimes.size();i){arrivalTime[i]{times[i][0],i};}vectorintemptyChair;vectorintfriendToChair(times.size());make_heap(arrivalTime.begin(),arrivalTime.end(),greater());vectorpairint,intleaveTime;intminChair0;intans0;for(inti0;itimes.size();i){// 取剩余最先到达的朋友intaTimearrivalTime[0].first;// 先把离开的朋友的椅子释放出来while(!empty(leaveTime)leaveTime[0].firstaTime){intlFriendIdxleaveTime[0].second;intlChairfriendToChair[lFriendIdx];emptyChair.push_back(lChair);push_heap(emptyChair.begin(),emptyChair.end(),greater());pop_heap(leaveTime.begin(),leaveTime.end(),greater());leaveTime.pop_back();}// 分配椅子intaChair-1;// 如果已分配过的椅子全都被占用直接取未分配的最小椅子编号if(empty(emptyChair)){aChairminChair;// 否则取小顶堆顶的椅子}else{aChairemptyChair[0];pop_heap(emptyChair.begin(),emptyChair.end(),greater());emptyChair.pop_back();}// 找到目标朋友的位置了intaFriendIdxarrivalTime[0].second;if(aFriendIdxtargetFriend){ansaChair;break;}// 将离开时间加入小顶堆friendToChair[aFriendIdx]aChair;leaveTime.push_back({times[arrivalTime[0].second][1],aFriendIdx});push_heap(leaveTime.begin(),leaveTime.end(),greater());// 将到达时间取出小顶堆pop_heap(arrivalTime.begin(),arrivalTime.end(),greater());arrivalTime.pop_back();}returnans;}};如果有n个朋友则此算法时间复杂度为O(nlogn)空间复杂度为O(n)。
LeetCode 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.length2 n 104^44times[i].length 21 arrivali leavingi 105^550 targetFriend n - 1每个 arrivali 时刻 互不相同 。我们可以用一个变量来记录已经分配的椅子的最大编号然后用一个小顶堆来管理曾分配出去但又释放掉的椅子到达时刻和离开时刻也可以用小顶堆来管理classSolution{public:intsmallestChair(vectorvectorinttimes,inttargetFriend){vectorpairint,intarrivalTime(times.size());for(inti0;itimes.size();i){arrivalTime[i]{times[i][0],i};}vectorintemptyChair;vectorintfriendToChair(times.size());make_heap(arrivalTime.begin(),arrivalTime.end(),greater());vectorpairint,intleaveTime;intminChair0;intans0;for(inti0;itimes.size();i){// 取剩余最先到达的朋友intaTimearrivalTime[0].first;// 先把离开的朋友的椅子释放出来while(!empty(leaveTime)leaveTime[0].firstaTime){intlFriendIdxleaveTime[0].second;intlChairfriendToChair[lFriendIdx];emptyChair.push_back(lChair);push_heap(emptyChair.begin(),emptyChair.end(),greater());pop_heap(leaveTime.begin(),leaveTime.end(),greater());leaveTime.pop_back();}// 分配椅子intaChair-1;// 如果已分配过的椅子全都被占用直接取未分配的最小椅子编号if(empty(emptyChair)){aChairminChair;// 否则取小顶堆顶的椅子}else{aChairemptyChair[0];pop_heap(emptyChair.begin(),emptyChair.end(),greater());emptyChair.pop_back();}// 找到目标朋友的位置了intaFriendIdxarrivalTime[0].second;if(aFriendIdxtargetFriend){ansaChair;break;}// 将离开时间加入小顶堆friendToChair[aFriendIdx]aChair;leaveTime.push_back({times[arrivalTime[0].second][1],aFriendIdx});push_heap(leaveTime.begin(),leaveTime.end(),greater());// 将到达时间取出小顶堆pop_heap(arrivalTime.begin(),arrivalTime.end(),greater());arrivalTime.pop_back();}returnans;}};如果有n个朋友则此算法时间复杂度为O(nlogn)空间复杂度为O(n)。
