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

雇佣 K 位工人的总代价

• 难度: medium
• 原始链接: https://leetcode.cn/problems/total-cost-to-hire-k-workers
• 标签: 优先级队列

解法一: 优先级队列

java

class Solution {
    public long totalCost(int[] costs, int k, int candidates) {
        PriorityQueue<Integer> leftQueue = new PriorityQueue<>((num1, num2) -> num1 - num2);
        PriorityQueue<Integer> rightQueue = new PriorityQueue<>((num1, num2) -> num1 - num2);
        int n = costs.length;
        int left = 0;
        int right = n - 1;
        for (int i = 0; i < candidates && left <= right; i++) {
            leftQueue.offer(costs[left++]);
            if (left <= right) {
                rightQueue.offer(costs[right--]);
            }
        }
        long ans = 0L;
        while (k-- > 0) {
            if (leftQueue.isEmpty() || !rightQueue.isEmpty() && leftQueue.peek() > rightQueue.peek()) {
                ans += rightQueue.poll();
                while (left <= right && rightQueue.size() < candidates) {
                    rightQueue.offer(costs[right--]);
                }
            } else {
                ans += leftQueue.poll();
                while (left <= right && leftQueue.size() < candidates) {
                    leftQueue.offer(costs[left++]);
                }
            }
        }
        return ans;
    }
}