跳至主要內容

2462. 雇佣 K 位工人的总代价

2462. 雇佣 K 位工人的总代价

🟠   🔖  数组 双指针 模拟 堆（优先队列）  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.

You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:

  • You will run k sessions and hire exactly one worker in each session.
  • In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
    • For example, if costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [_3,2_ ,7,7,_1,2_].
    • In the second hiring session, we will choose 1st worker because they have the same lowest cost as 4th worker but they have the smallest index [_3,2_ ,7,_7,2_]. Please note that the indexing may be changed in the process.
  • If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
  • A worker can only be chosen once.

Return the total cost to hire exactlyk workers.

Example 1:

Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4

Output: 11

Explanation: We hire 3 workers in total. The total cost is initially 0.

  • In the first hiring round we choose the worker from [17,12,10,2 ,7,2,11,20,8]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2.
  • In the second hiring round we choose the worker from [17,12,10,7 ,2,11,20,8]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4.
  • In the third hiring round we choose the worker from [17,12,10,7,11,20,8]. The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the worker with index 3 was common in the first and last four workers.

The total hiring cost is 11.

Example 2:

Input: costs = [1,2,4,1], k = 3, candidates = 3

Output: 4

Explanation: We hire 3 workers in total. The total cost is initially 0.

  • In the first hiring round we choose the worker from [1,2,4,1]. The lowest cost is 1, and we break the tie by the smallest index, which is 0. The total cost = 0 + 1 = 1. Notice that workers with index 1 and 2 are common in the first and last 3 workers.
  • In the second hiring round we choose the worker from [2,4,1]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2.
  • In the third hiring round there are less than three candidates. We choose the worker from the remaining workers [2,4]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4.

The total hiring cost is 4.

Constraints:

  • 1 <= costs.length <= 105
  • 1 <= costs[i] <= 10^5
  • 1 <= k, candidates <= costs.length

题目大意

给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。

同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：

  • 总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。
  • 在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
    • 比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 [_3,2_ ,7,7,_1 ,2_] 。
    • 第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[_3,2_ ,7,_7,2_] 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
  • 如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
  • 一位工人只能被选择一次。

返回雇佣恰好 k 位工人的总代价。

示例 1：

输入： costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4

输出： 11

解释： 我们总共雇佣 3 位工人。总代价一开始为 0 。

  • 第一轮雇佣，我们从 [17,12,10,2 ,7,2,11,20,8] 中选择。最小代价是 2 ，有两位工人，我们选择下标更小的一位工人，即第 3 位工人。总代价是 0 + 2 = 2 。
  • 第二轮雇佣，我们从 [17,12,10,7 ,2,11,20,8] 中选择。最小代价是 2 ，下标为 4 ，总代价是 2 + 2 = 4 。
  • 第三轮雇佣，我们从 [17,12,10,7,11,20,8] 中选择，最小代价是 7 ，下标为 3 ，总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。

总雇佣代价是 11 。

示例 2：

输入： costs = [1,2,4,1], k = 3, candidates = 3

输出： 4

解释： 我们总共雇佣 3 位工人。总代价一开始为 0 。

  • 第一轮雇佣，我们从 [1,2,4,1] 中选择。最小代价为 1 ，有两位工人，我们选择下标更小的一位工人，即第 0 位工人，总代价是 0 + 1 = 1 。注意，下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。
  • 第二轮雇佣，我们从 [2,4,1] 中选择。最小代价为 1 ，下标为 2 ，总代价是 1 + 1 = 2 。
  • 第三轮雇佣，少于 3 位工人，我们从剩余工人 [2,4] 中选择。最小代价是 2 ，下标为 0 。总代价为 2 + 2 = 4 。

总雇佣代价是 4 。

提示：

  • 1 <= costs.length <= 105
  • 1 <= costs[i] <= 10^5
  • 1 <= k, candidates <= costs.length

解题思路

双优先队列 + 贪心

  1. 利用双优先队列：

    • 使用两个最小堆分别维护两端的候选人：
      • 一个堆存储从左边选的候选人。
      • 一个堆存储从右边选的候选人。
    • 这允许我们快速选出当前费用最小的工人。

  2. 滑动窗口：

    • 比较两个堆的堆顶，选择费用较小的工人并将其从数组中移除。
    • 滑动窗口，如果还有新的候选人，将新的候选人加入到对应的堆，使得始终有足够的候选人可供选择。

复杂度分析

  • 时间复杂度：

    • 初始化堆：左堆和右堆各插入最多 candidates 个元素，时间复杂度为 O(candidates * log candidates)。
    • 雇佣 k 位工人：每次选择和更新堆操作的复杂度为 O(log candidates)，总共 k 次。
    • 总时间复杂度为： O((candidates + k) * log candidates)

  • 空间复杂度：

    • 两个堆的空间复杂度为 O(candidates)。
    • 总空间复杂度为 O(candidates)。

代码

/**
 * @param {number[]} costs
 * @param {number} k
 * @param {number} candidates
 * @return {number}
 */
var totalCost = function (costs, k, candidates) {
	let leftHeap = new MinHeap(); // 左堆
	let rightHeap = new MinHeap(); // 右堆

	let left = 0,
		right = costs.length - 1; // 左右指针

	// 初始化左堆
	for (let i = 0; i < candidates && left <= right; i++) {
		leftHeap.insert(costs[left++]);
	}

	// 初始化右堆
	for (let i = 0; i < candidates && left <= right; i++) {
		rightHeap.insert(costs[right--]);
	}

	let totalCost = 0; // 总成本

	// 雇佣 k 位工人
	for (let i = 0; i < k; i++) {
		if (
			!rightHeap.isEmpty() &&
			(leftHeap.isEmpty() || rightHeap.front() < leftHeap.front())
		) {
			totalCost += rightHeap.pop();

			// 从右侧加入新的候选人
			if (left <= right) {
				rightHeap.insert(costs[right--]);
			}
		} else {
			totalCost += leftHeap.pop();

			// 从左侧加入新的候选人
			if (left <= right) {
				leftHeap.insert(costs[left++]);
			}
		}
	}
	return totalCost;
};

// 最小堆
class MinHeap {
	constructor() {
		this.heap = [];
	}
	insert(num) {
		this.heap.push(num);
		this.heapifyUp(this.heap.length - 1);
	}
	pop() {
		if (this.heap.length == 0) return null;
		const top = this.heap[0];
		const last = this.heap.pop();
		if (this.heap.length > 0) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}
	size() {
		return this.heap.length;
	}
	isEmpty() {
		return this.heap.length == 0;
	}
	front() {
		if (this.heap.length) return this.heap[0];
		return null;
	}
	heapifyDown(i) {
		const left = i * 2 + 1,
			right = i * 2 + 2;
		let min = i;
		if (left < this.heap.length && this.heap[left] < this.heap[min]) {
			min = left;
		}
		if (right < this.heap.length && this.heap[right] < this.heap[min]) {
			min = right;
		}
		if (i !== min) {
			[this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
			this.heapifyDown(min);
		}
	}
	heapifyUp(i) {
		while (i) {
			const parent = ((i - 1) / 2) | 0;
			if (this.heap[i] < this.heap[parent]) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
}

相关题目

题号标题题解标签难度力扣
253会议室 II 🔒贪心 数组 双指针 3+🟠🀄️open in new window 🔗open in new window
2532过桥的时间数组 模拟 堆（优先队列）🔴🀄️open in new window 🔗open in new window
Copyright © 2024 2xiao