做章的网站,安徽建站平台,网页设计的培训机构,做网站怎么插音乐文章目录1. 题目2. 解题1. 题目
有 n 个朋友在举办一个派对#xff0c;这些朋友从 0 到 n - 1 编号。 派对里有 无数 张椅子#xff0c;编号为 0 到 infinity 。 当一个朋友到达派对时#xff0c;他会占据 编号最小 且未被占据的椅子。
比方说#xff0c;当一个朋友到达时…
文章目录1. 题目2. 解题1. 题目
有 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 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
使用 set 对 离开时间拿的号码 自动排序当前人要取号之前先将时间到了要离开的人的号放回再从没有取的号码里拿出最小的使用 set 实现
class Solution {
public:int smallestChair(vectorvectorint times, int targetFriend) {int n times.size();vectorint id(n);iota(id.begin(), id.end(), 0); // 编号 0 - n-1sort(id.begin(), id.end(), [](auto a, auto b){if(times[a][0] times[b][0])return times[a][1] times[b][1];return times[a][0] times[b][0];}); // 排序先来的先取号先走的先放回号码setint untake(id.begin(), id.end()); // 没拿的号码setpairint,int leaveTime; // 离开时间拿的号码自动排序时间早的先离开for(auto idx : id){while(!leaveTime.empty() (*leaveTime.begin()).first times[idx][0]) { // 到达之前有人离开int num (*leaveTime.begin()).second;//拿的号码untake.insert(num);//放回号码leaveTime.erase(leaveTime.begin());//离开了}if(idx targetFriend)return *untake.begin();int takeNum *untake.begin();//分配号码untake.erase(takeNum);leaveTime.insert({times[idx][1], takeNum});}return -1;}
};264 ms 71.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
