LeetCode Entry
2462. Total Cost to Hire K Workers
The sum of the smallest cost from suffix and prefix of a costs size of candidates in k iterations
2462. Total Cost to Hire K Workers medium
blog post
substack
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/257
Problem TLDR
The sum of the smallest cost from suffix and prefix of a costs size of candidates in k iterations
Intuition
Description of the problem is rather ambiguous: we actually need to consider candidates count of items from the head and from the tail of the costs array. Then we can use PriorityQueue to choose the minimum and adjust two pointers lo and hi.
Approach
- use separate condition, when
2 * candidates >= costs.size - careful with indexes, check yourself by doing dry run
- we can use separate variable
takenLandtakenRor just use queue’s sizes to minify the code
Complexity
-
Time complexity: \(O(nlog(n))\)
-
Space complexity: \(O(n)\)
Code
fun totalCost(costs: IntArray, k: Int, candidates: Int): Long {
val pqL = PriorityQueue<Int>()
val pqR = PriorityQueue<Int>()
var lo = 0
var hi = costs.lastIndex
var sum = 0L
var count = 0
if (2 * candidates >= costs.size) while (lo <= hi) pqL.add(costs[lo++])
while (pqL.size < candidates && lo <= hi) pqL.add(costs[lo++])
while (pqR.size < candidates && lo < hi) pqR.add(costs[hi--])
while (lo <= hi && count++ < k) {
if (pqR.peek() < pqL.peek()) {
sum += pqR.poll()
pqR.add(costs[hi--])
} else {
sum += pqL.poll()
pqL.add(costs[lo++])
}
}
while (pqR.isNotEmpty()) pqL.add(pqR.poll())
while (count++ < k && pqL.isNotEmpty()) sum += pqL.poll()
return sum
}