原文链接: https://leetcode-cn.com/problems/the-number-of-the-smallest-unoccupied-chair
英文原文
There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.
- For example, if chairs
0,1, and5are occupied when a friend comes, they will sit on chair number2.
When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.
You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.
Return the chair number that the friend numbered targetFriend will sit on.
Example 1:
Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1 Output: 1 Explanation: - Friend 0 arrives at time 1 and sits on chair 0. - Friend 1 arrives at time 2 and sits on chair 1. - Friend 1 leaves at time 3 and chair 1 becomes empty. - Friend 0 leaves at time 4 and chair 0 becomes empty. - Friend 2 arrives at time 4 and sits on chair 0. Since friend 1 sat on chair 1, we return 1.
Example 2:
Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0 Output: 2 Explanation: - Friend 1 arrives at time 1 and sits on chair 0. - Friend 2 arrives at time 2 and sits on chair 1. - Friend 0 arrives at time 3 and sits on chair 2. - Friend 1 leaves at time 5 and chair 0 becomes empty. - Friend 2 leaves at time 6 and chair 1 becomes empty. - Friend 0 leaves at time 10 and chair 2 becomes empty. Since friend 0 sat on chair 2, we return 2.
Constraints:
n == times.length2 <= n <= 104times[i].length == 21 <= arrivali < leavingi <= 1050 <= targetFriend <= n - 1- Each
arrivalitime is distinct.
中文题目
有 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 <= 104times[i].length == 21 <= arrivali < leavingi <= 1050 <= targetFriend <= n - 1- 每个
arrivali时刻 互不相同 。
通过代码
高赞题解
5805. 最小未被占据椅子的编号-双周赛第二题
第二题，看着题目好像说了蛮多的，其实就是一群人过来抢凳子，大家都先做编号小的。每个人的进场和离场时间不一样。
感觉可以给这些人依据进场顺序排个序，看了看数据量还算可以接受，果断上模拟，再拼一波手速。
class Solution {
public:
int smallestChair(vector<vector<int>>& times, int targetFriend) {
const int length = times.size();
pair<int, int> array[10000]; //大家进场和出场的时间
int cher[10000]; //椅子，存的值是将被占用到的时间
memset(cher, 0, sizeof(cher)); //椅子，现在还没有人坐
int Index = 0;
vector<vector<int>>::iterator itB = times.begin(), itE = times.end();
while(itB != itE){
array[Index].first = *((*itB).begin()); //把进场和出场的时间赋值给我们的pair
array[Index].second = *((*itB).end() - 1);
++Index;
++itB;
}
int tmp = array[targetFriend].first; //第targetFriend入场时间
sort(array, array + length); //排下序，让最先进场的人排到遍历的最前面
for(int i = 0; i < length; ++i){
int j = 0;
while(cher[j] != 0 && cher[j] > array[i].first){//从小编号椅子开始遍历查看是否能坐
++j;
}
if(array[i].first == tmp) //第targetFriend的入场时间到了
return j; //返回他的作为编号
cher[j] = array[i].second; //椅子里存的值是它主人离开的时间
}
return 0;
}
};统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 3092 | 7764 | 39.8% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
