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

🟠   🔖  数组 哈希表 堆（优先队列）  🔗 力扣 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 数组。

代码

优先队列

/**
 * @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;
		}
	}
}

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

/**
 * @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); // 保持椅子编号的顺序
		}
	}
};