Total Cost to Hire K Workers - Practice Coding Problems

Total Cost to Hire K Workers - Problem

You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the i-th worker.

You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:

You will run k sessions and hire exactly one worker in each session.
In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break the tie by the smallest index.
A worker can only be chosen once.

Return the total cost to hire exactly k workers.

Input & Output

Example 1 — Basic Case

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

› Output: 11

💡 Note: Session 1: First 4 = [17,12,10,2], Last 4 = [2,11,20,8]. Pick min = 2 (index 3). Session 2: First 4 = [17,12,10,7], Last 4 = [2,11,20,8]. Pick min = 2 (index 5). Session 3: First 4 = [17,12,10,7], Last 3 = [11,20,8]. Pick min = 7. Total = 2+2+7 = 11

Example 2 — Small Array

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

› Output: 4

💡 Note: Since candidates=3 covers most of array, we pick 3 cheapest: 1, 1, 2. Total = 1+1+2 = 4

Example 3 — Equal Costs

$ Input: costs = [2,2,2,2,2], k = 2, candidates = 2

› Output: 4

💡 Note: All costs are equal, so we pick by smallest index. Choose indices 0 and 1, both cost 2. Total = 2+2 = 4

Constraints

1 ≤ k, candidates ≤ costs.length ≤ 10⁵
1 ≤ costs[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of worker costs with k hiring sessions

Process

Pick cheapest from first/last candidates each session

Output

Sum of costs for k hired workers

Key Takeaway

🎯 Key Insight: Use two heaps to efficiently find the cheapest worker from candidate pools at both ends

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to maintain two heaps for candidates from both ends of the array. The optimal two heaps approach efficiently tracks the cheapest workers using priority queues. Time: O(k log candidates), Space: O(candidates)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(k × n)	O(n)	Simulate each hiring session by checking all eligible candidates
Two Heaps Approach	O(k log candidates)	O(candidates)	Use two priority queues to efficiently track cheapest candidates from both ends

Brute Force Simulation — Algorithm Steps

Step 1: For each hiring session, identify eligible workers from first/last candidates
Step 2: Find minimum cost worker among eligible ones, breaking ties by index
Step 3: Mark worker as hired and add cost to total

Visualization

Tap to expand

Step-by-Step Walkthrough

Session 1

Scan first and last candidates to find minimum

Session 2

Mark hired worker, repeat scan

Continue

Repeat until k workers hired

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>

long long solution(int* costs, int costsSize, int k, int candidates) {
    bool* hired = (bool*)calloc(costsSize, sizeof(bool));
    long long totalCost = 0;
    
    for (int session = 0; session < k; session++) {
        int minCost = INT_MAX;
        int minIdx = -1;
        
        // Check first candidates workers
        int count = 0;
        for (int i = 0; i < costsSize && count < candidates; i++) {
            if (!hired[i]) {
                if (costs[i] < minCost || (costs[i] == minCost && i < minIdx)) {
                    minCost = costs[i];
                    minIdx = i;
                }
                count++;
            }
        }
        
        // Check last candidates workers
        count = 0;
        for (int i = costsSize - 1; i >= 0 && count < candidates; i--) {
            if (!hired[i]) {
                if (costs[i] < minCost || (costs[i] == minCost && i < minIdx)) {
                    minCost = costs[i];
                    minIdx = i;
                }
                count++;
            }
        }
        
        hired[minIdx] = true;
        totalCost += minCost;
    }
    
    free(hired);
    return totalCost;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int costs[50000];
    int costsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        costs[costsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k, candidates;
    scanf("%d", &k);
    scanf("%d", &candidates);
    
    long long result = solution(costs, costsSize, k, candidates);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × n)

For each of k hiring sessions, we scan up to n workers to find minimum

✓ Linear Growth

Space Complexity

O(n)

Boolean array to track hired workers

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

834 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler