class Solution {
public:
int smallestChair(vector<vector<int>>& times, int targetFriend) {
}
};
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 <= 104times[i].length == 21 <= arrivali < leavingi <= 1050 <= targetFriend <= n - 1arrivali 时刻 互不相同 。原站题解
java 解法, 执行用时: 68 ms, 内存消耗: 49.3 MB, 提交时间: 2023-09-26 20:21:29
class Solution {
public int smallestChair(int[][] times, int targetFriend) {
int n = times.length;
int[][] arrivals = new int[n][2];
int[][] leaves = new int[n][2];
for (int i = 0; i < n; i++) {
arrivals[i][0] = times[i][0];
arrivals[i][1] = i;
leaves[i][0] = times[i][1];
leaves[i][1] = i;
}
Arrays.sort(arrivals, (a, b) -> a[0] - b[0]);
Arrays.sort(leaves, (a, b) -> a[0] - b[0]);
Map<Integer, Integer> map = new HashMap<>();
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
pq.offer(i);
}
int j = 0;
for (int[] arrival : arrivals) {
while (j < n && leaves[j][0] <= arrival[0]) {
pq.offer(map.get(leaves[j][1]));
j++;
}
map.put(arrival[1], pq.poll());
if (arrival[1] == targetFriend) {
return map.get(targetFriend);
}
}
return -1;
}
}
python3 解法, 执行用时: 188 ms, 内存消耗: 21 MB, 提交时间: 2023-09-26 20:21:12
from heapq import heappop, heappush
class Solution:
def smallestChair(self, times: List[List[int]], targetFriend: int) -> int:
n = len(times)
arrival = [] # 到达操作的时刻和对应的人
leaving = [] # 离开操作的时刻和对应的人
for i in range(n):
arrival.append((times[i][0], i))
leaving.append((times[i][1], i))
# 将到达与离开操作按照时间升序排序以方便模拟
arrival.sort()
leaving.sort()
available = list(range(n)) # 未被占据的椅子
seats = {} # 每个人占据的椅子
# 双指针模拟
j = 0
for time, person in arrival:
# 处理到达时间与之前的离开操作
# 将释放的椅子加入未被占据椅子中
while j < n and leaving[j][0] <= time:
heappush(available, seats[leaving[j][1]])
j += 1
# 处理到达操作
# 占据当前编号最小且未被占据的椅子
seat = heappop(available)
seats[person] = seat
if person == targetFriend:
# 如果当前人为目标，则返回对应的椅子
return seat
return -1
cpp 解法, 执行用时: 180 ms, 内存消耗: 65.1 MB, 提交时间: 2023-09-26 20:20:56
class Solution {
public:
int smallestChair(vector<vector<int>>& times, int targetFriend) {
int n = times.size();
vector<pair<int, int>> arrival; // 到达操作的时刻和对应的人
vector<pair<int, int>> leaving; // 离开操作的时刻和对应的人
for (int i = 0; i < n; ++i){
arrival.emplace_back(times[i][0], i);
leaving.emplace_back(times[i][1], i);
}
// 将到达与离开操作按照时间升序排序以方便模拟
sort(arrival.begin(), arrival.end());
sort(leaving.begin(), leaving.end());
priority_queue<int, vector<int>, greater<int>> available; // 未被占据的椅子
for (int i = 0; i < n; ++i){
available.push(i);
}
unordered_map<int, int> seats; // 每个人占据的椅子
// 双指针模拟
int j = 0;
for (auto&& [time, person] : arrival){
// 处理到达时间与之前的离开操作
// 将释放的椅子加入未被占据椅子中
while (j < n && leaving[j].first <= time){
available.push(seats[leaving[j].second]);
++j;
}
// 处理到达操作
// 占据当前编号最小且未被占据的椅子
int seat = available.top();
seats[person] = seat;
available.pop();
if (person == targetFriend){
// 如果当前人为目标，则返回对应的椅子
return seat;
}
}
return -1;
}
};
golang 解法, 执行用时: 168 ms, 内存消耗: 31.4 MB, 提交时间: 2023-09-26 20:20:21
func smallestChair(times [][]int, targetFriend int) int {
// 按时间顺序，记录每个到达事件和离开事件相对应的朋友编号
events := make([][2][]int, 1e5+1)
for i, t := range times {
l, r := t[0], t[1]
events[l][1] = append(events[l][1], i) // 朋友到达
events[r][0] = append(events[r][0], i) // 朋友离开
}
// 初始化未被占据的椅子
n := len(times)
unoccupied := hp{make([]int, n)}
for i := range unoccupied.IntSlice {
unoccupied.IntSlice[i] = i
}
// 按时间顺序扫描每个事件
belong := make([]int, n)
for _, e := range events {
for _, id := range e[0] { // 朋友离开
heap.Push(&unoccupied, belong[id]) // 返还椅子
}
for _, id := range e[1] { // 朋友到达
belong[id] = heap.Pop(&unoccupied).(int) // 记录占据该椅子的朋友编号
if id == targetFriend {
return belong[id]
}
}
}
return 0
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
golang 解法, 执行用时: 148 ms, 内存消耗: 28.2 MB, 提交时间: 2023-09-26 20:20:10
const wLog = 5 + bits.UintSize>>6
const wMask = bits.UintSize - 1
// bitset， 用 0 表示空椅子，1 表示椅子被占用，这样可以在 bitset 内暴力找第一个空椅子。
func smallestChair(times [][]int, targetFriend int) int {
// 按时间顺序，记录每个到达事件和离开事件相对应的朋友编号
events := make([][2][]int, 1e5+1)
for i, t := range times {
l, r := t[0], t[1]
events[l][1] = append(events[l][1], i) // 朋友到达
events[r][0] = append(events[r][0], i) // 朋友离开
}
// 初始化未被占据的椅子
n := len(times)
bitset := make([]uint, n>>wLog+1)
flip := func(p int) { bitset[p>>wLog] ^= 1 << (p & wMask) }
// 按时间顺序扫描每个事件
belong := make([]int, n)
for _, e := range events {
for _, id := range e[0] { // 朋友离开
flip(belong[id]) // 返还椅子
}
for _, id := range e[1] { // 朋友到达
for i, mask := range bitset { // 暴力找未被占据的椅子
if ^mask != 0 {
belong[id] = i<<wLog | bits.TrailingZeros(^mask) // 记录占据该椅子的朋友编号
break
}
}
if id == targetFriend {
return belong[id]
}
flip(belong[id])
}
}
return 0
}