Skip to content

2462. Total Cost to Hire K Workers

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  long long totalCost(vector<int>& costs, int k, int candidates) {
    long ans = 0;
    int i = 0;
    int j = costs.size() - 1;
    priority_queue<int, vector<int>, greater<>> minHeapL;
    priority_queue<int, vector<int>, greater<>> minHeapR;

    for (int hired = 0; hired < k; ++hired) {
      while (minHeapL.size() < candidates && i <= j)
        minHeapL.push(costs[i++]);
      while (minHeapR.size() < candidates && i <= j)
        minHeapR.push(costs[j--]);
      if (minHeapL.empty())
        ans += minHeapR.top(), minHeapR.pop();
      else if (minHeapR.empty())
        ans += minHeapL.top(), minHeapL.pop();
      // Both `minHeapL` and `minHeapR` are not empty.
      else if (minHeapL.top() <= minHeapR.top())
        ans += minHeapL.top(), minHeapL.pop();
      else
        ans += minHeapR.top(), minHeapR.pop();
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public long totalCost(int[] costs, int k, int candidates) {
    long ans = 0;
    int i = 0;
    int j = costs.length - 1;
    Queue<Integer> minHeapL = new PriorityQueue<>();
    Queue<Integer> minHeapR = new PriorityQueue<>();

    for (int hired = 0; hired < k; ++hired) {
      while (minHeapL.size() < candidates && i <= j)
        minHeapL.offer(costs[i++]);
      while (minHeapR.size() < candidates && i <= j)
        minHeapR.offer(costs[j--]);
      if (minHeapL.isEmpty())
        ans += minHeapR.poll();
      else if (minHeapR.isEmpty())
        ans += minHeapL.poll();
      // Both `minHeapL` and `minHeapR` are not empty.
      else if (minHeapL.peek() <= minHeapR.peek())
        ans += minHeapL.poll();
      else
        ans += minHeapR.poll();
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def totalCost(self, costs: list[int], k: int, candidates: int) -> int:
    ans = 0
    i = 0
    j = len(costs) - 1
    minHeapL = []  # First half
    minHeapR = []  # Second half

    for _ in range(k):
      while len(minHeapL) < candidates and i <= j:
        heapq.heappush(minHeapL, costs[i])
        i += 1
      while len(minHeapR) < candidates and i <= j:
        heapq.heappush(minHeapR, costs[j])
        j -= 1
      if not minHeapL:
        ans += heapq.heappop(minHeapR)
      elif not minHeapR:
        ans += heapq.heappop(minHeapL)
      # Both `minHeapL` and `minHeapR` are not empty.
      elif minHeapL[0] <= minHeapR[0]:
        ans += heapq.heappop(minHeapL)
      else:
        ans += heapq.heappop(minHeapR)

    return ans