Hiring From Both Ends

MediumHeap / Priority Queue

Problem

Applicants stand in a line; costs[i] is the salary applicant i asks for. The company runs k hiring rounds. In each round it looks only at the first candidates applicants and the last candidates applicants still in line (fewer if the line is short; an applicant in both groups is counted once), hires the cheapest of them, breaking ties by the smallest original index, and removes that person from the line.

Return the total salary of the k people hired.

Example 1

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

Round 1: front [17, 12, 10, 2] and back [2, 11, 20, 8] both offer cost 2; the front one (index 3) has the smaller index. Round 2: the front window now includes 7 (index 4), and the back's 2 (index 5) is cheapest. Round 3: front [17, 12, 10, 7], back [11, 20, 8] → 7. Total 2 + 2 + 7 = 11.

Example 2

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

The groups overlap: everyone is visible. Hire 1 (index 0), 1 (index 3), then 2.

Constraints

  • 1 ≤ costs.length ≤ 10^5
  • 1 ≤ costs[i] ≤ 10^5
  • 1 ≤ k, candidates ≤ costs.length

Hint

Show the first hint

Each round needs the cheapest applicant in each of two small windows, and the windows refill from the middle of the line.

Walkthrough

How to approach it

01Clarify before coding

  • If the front and back groups overlap, is an applicant considered twice? No, once.
  • Ties? Smallest original index, so on equal cost the front group wins.
  • Can k be equal to n? Yes; eventually every applicant is visible.

02Brute force

Each round, build both windows from the current line, scan them for the cheapest, and remove that applicant from the list.

Cost: O(k · (candidates + n)) because of scanning and list removal: up to 10^10.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.