669. Total Cost to Hire K Workers
A company must fill k positions from a line of applicants. costs[i] is the salary worker i demands, listed in application order.
Hiring runs in k sessions, one hire per session. In each session you may only interview the first candidates workers and the last candidates workers still in the line (when fewer than 2 × candidates remain, everyone left is visible). Among the visible workers you must hire the one demanding the lowest salary, breaking ties by the smaller original index. The hired worker leaves the line before the next session.
Return the total salary paid across all k hires.
Example 1:
Input: costs = [3, 2, 7, 7, 1, 2], k = 2, candidates = 2
Output: 3
Explanation: Session 1 sees the front pair {3, 2} and the back pair {1, 2}; the cheapest bid is 1 (index 4), so that worker is hired. Session 2 sees {3, 2} and {7, 2}: the low bid 2 is tied between index 1 and index 5, and the smaller index 1 wins. Total 1 + 2 = 3.
Example 2:
Input: costs = [5, 6, 7], k = 3, candidates = 4
Output: 18
Explanation: candidates exceeds the line length, so every session sees everyone remaining. The hires go 5, then 6, then 7 — the whole line — for a total of 18.
Constraints:
- 1 ≤ costs.length ≤ 10⁵
- 1 ≤ costs[i] ≤ 10⁵
- 1 ≤ k, candidates ≤ costs.length
Hints:
Literal simulation works: each session, scan the first candidates and the last candidates of the remaining line for the minimum, remove the winner, repeat. Count what that re-scanning costs across k sessions before optimizing.
Between sessions only the edges of the two visible windows change. Keep two min-heaps — one over the front section, one over the back — plus two pointers fencing off the untouched middle. Each session: take the smaller heap top (front wins ties), then refill that heap from the middle. Guard every push with i <= j so a middle worker is never inserted twice.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: costs = [3, 2, 7, 7, 1, 2], k = 2, candidates = 2
Expected output: 3