Skip to content

Latest commit

 

History

History
356 lines (291 loc) · 11.6 KB

1942.md

File metadata and controls

356 lines (291 loc) · 11.6 KB
title description keywords
1942. 最小未被占据椅子的编号
LeetCode 1942. 最小未被占据椅子的编号题解，The Number of the Smallest Unoccupied Chair，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
1942. 最小未被占据椅子的编号
最小未被占据椅子的编号
The Number of the Smallest Unoccupied Chair
解题思路
数组
哈希表
堆（优先队列）

1942. 最小未被占据椅子的编号

🟠 Medium  🔖  数组 哈希表 堆（优先队列）  🔗 力扣 LeetCode

题目

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, and 5 are occupied when a friend comes, they will sit on chair number 2.

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 _thechair 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.length
  • 2 <= n <= 10^4
  • times[i].length == 2
  • 1 <= arrivali < leavingi <= 10^5
  • 0 <= targetFriend <= n - 1
  • Each arrivali time 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.length
  • 2 <= n <= 10^4
  • times[i].length == 2
  • 1 <= arrivali < leavingi <= 10^5
  • 0 <= targetFriend <= n - 1
  • 每个 arrivali 时刻 互不相同 。

解题思路

思路一：优先队列

这个问题可以用事件驱动的方式解决。将每个人的到达和离开事件都看作一个事件，并按照时间顺序进行处理。

可以使用一个优先队列（最小堆）来存储每个椅子的状态，这样可以随时找到最小编号的空椅子。

  • 首先将所有到达和离开的时间按事件排序。
  • 对每一个到达事件，从优先队列中取出最小的空椅子编号，分配给当前人。
  • 对于每一个离开事件，将该人坐的椅子归还到优先队列。
  • 当处理到 targetFriend 时，记录下他坐的椅子编号并返回。

复杂度分析

  • 时间复杂度：O(n log n)，其中 n 是参加聚会的总人数。
    • 事件存储和遍历事件的复杂度为 O(n)。
    • 排序事件的复杂度为 O(n log n)，其中 n 是事件的数量。
    • 堆操作（插入和删除）在每次到达和离开事件时操作最小堆的复杂度为 O(log n)。因此，对于 2n 个事件，堆操作的总复杂度为 O(n log n)。
  • 空间复杂度：O(n)，主要用于存储到达和离开的事件，以及优先队列。
    • events 数组存储 2n 个事件，因此空间复杂度为 O(n)。
    • occupied Map 存储最多 n 个成员的信息，因此也是 O(n)。
    • chairs 最小堆存储 n 把椅子，因此为 O(n)。

思路二：数组模拟优先队列 + 性能优化

如果觉得优先队列类的定义较为繁琐，也可以用数组来模拟优先队列，使用 sort() 方法对每次离开事件后释放的椅子进行排序。

但是由于 sort() 方法的复杂度为 O(n log n)，且每次都要重新排序，这意味着代码整体的时间复杂度将变为 O(n^2 log n)，因为对 n 个事件排序 n 次都会调用 sort()。

为了避免超时，要加入了一些优化处理，如：

  • events 中只存储在 targetFriend 到达之前发生的到达和离开事件，之后的事件不需要关心；
  • 记录 targetFriend 到达之前需要的椅子数量，只对需要的椅子进行排序，避免椅子释放回优先队列时超时；

复杂度分析

  • 时间复杂度：O(n^2 log n)，其中 n 是参加聚会的总人数
    • 事件存储和遍历事件的复杂度为 O(n)。
    • events 排序的复杂度为 O(n log n)，其中 n 是事件的数量。
    • chairs 排序的复杂度为 O(n log n)。因此，对于 2n 个事件排序的总复杂度为 O(n^2 log n)。
  • 空间复杂度：O(n)，主要用于存储到达和离开的事件，以及 chairs 数组。

代码

::: code-tabs @tab 优先队列

/**
 * @param {number[][]} times
 * @param {number} targetFriend
 * @return {number}
 */
var smallestChair = function (times, targetFriend) {
	const targetArrive = times[targetFriend][0];
	let events = [];

	// 把所有到达和离开的时间作为事件存储
	for (let i = 0; i < times.length; i++) {
		events.push([times[i][0], 'arrive', i]);
		events.push([times[i][1], 'leave', i]);
	}

	// 按时间排序，如果时间相同，离开事件先处理
	events.sort((a, b) =>
		a[0] == b[0] ? (a[1] === 'leave' ? -1 : 1) : a[0] - b[0]
	);

	let chairs = new MinHeap(); // 使用最小堆来模拟椅子的编号顺序
	let occupied = new Map(); // 存储当前占用椅子的情况
	for (let i = 0; i < times.length; i++) {
		chairs.push(i); // 初始化椅子的编号 0 到 n-1
	}

	// 遍历事件
	for (let [time, type, idx] of events) {
		if (type == 'arrive') {
			let chair = chairs.pop(); // 拿到最小编号的空椅子
			occupied.set(idx, chair); // 标记这个人占用的椅子

			if (idx == targetFriend) {
				return chair; // 如果是目标人，直接返回椅子编号
			}
		} else {
			let chair = occupied.get(idx); // 找到离开的人对应的椅子
			chairs.push(chair); // 椅子释放，放回最小堆
		}
	}
};

class MinHeap {
	constructor() {
		this.heap = [];
	}

	// 插入元素
	push(val) {
		this.heap.push(val);
		this.heapifyUp(this.heap.length - 1);
	}

	// 弹出堆顶元素
	pop() {
		if (this.size() === 1) return this.heap.pop();
		const top = this.heap[0];
		this.heap[0] = this.heap.pop();
		this.heapifyDown(0);
		return top;
	}

	// 返回堆顶元素
	peek() {
		return this.heap[0];
	}

	// 堆大小
	size() {
		return this.heap.length;
	}

	// 上浮操作
	heapifyUp(index) {
		while (index > 0) {
			let parentIndex = Math.floor((index - 1) / 2);
			if (this.heap[parentIndex] <= this.heap[index]) break;
			[this.heap[parentIndex], this.heap[index]] = [
				this.heap[index],
				this.heap[parentIndex]
			];
			index = parentIndex;
		}
	}

	// 下沉操作
	heapifyDown(index) {
		const length = this.heap.length;
		while (true) {
			let leftIndex = 2 * index + 1;
			let rightIndex = 2 * index + 2;
			let smallestIndex = index;

			if (
				leftIndex < length &&
				this.heap[leftIndex] < this.heap[smallestIndex]
			) {
				smallestIndex = leftIndex;
			}
			if (
				rightIndex < length &&
				this.heap[rightIndex] < this.heap[smallestIndex]
			) {
				smallestIndex = rightIndex;
			}
			if (smallestIndex === index) break;
			[this.heap[smallestIndex], this.heap[index]] = [
				this.heap[index],
				this.heap[smallestIndex]
			];
			index = smallestIndex;
		}
	}
}

@tab 数组模拟优先队列 + 性能优化

/**
 * @param {number[][]} times
 * @param {number} targetFriend
 * @return {number}
 */
var smallestChair = function (times, targetFriend) {
	const targetArrive = times[targetFriend][0];
	let events = [],
		chairCount = 0; // 记录 targetFriend 到达之前需要的椅子数，避免排序超时

	// 把所有到达和离开的时间作为事件存储
	// 注意只存储在 targetFriend 到达之前发生的到达和离开事件，避免排序超时
	for (let i = 0; i < times.length; i++) {
		if (times[i][0] <= targetArrive) {
			chairCount++;
			events.push([times[i][0], 'arrive', i]);
			if (times[i][1] <= targetArrive) {
				events.push([times[i][1], 'leave', i]);
				chairCount--;
			}
		}
	}

	// 按时间排序，如果时间相同，离开事件先处理
	events.sort((a, b) =>
		a[0] == b[0] ? (a[1] === 'leave' ? -1 : 1) : a[0] - b[0]
	);

	let chairs = [...Array(chairCount).keys()]; // 生成从 0 到 chairCount - 1 的椅子编号

	let occupied = new Map(); // 存储当前占用椅子的情况
	for (let [time, type, idx] of events) {
		if (type == 'arrive') {
			let chair = chairs.shift(); // 拿到最小编号的空椅子
			occupied.set(idx, chair); // 标记这个人占用的椅子

			if (idx == targetFriend) {
				return chair; // 如果是目标人，直接返回椅子编号
			}
		} else {
			let chair = occupied.get(idx); // 找到离开的人对应的椅子
			chairs.push(chair); // 椅子释放，放回优先队列
			chairs.sort((a, b) => a - b); // 保持椅子编号的顺序
		}
	}
};

:::