We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Total Cost to Hire K Workers

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires maintaining a selection of candidates from both ends of the array.
  • A priority queue (min-heap) can be used to efficiently retrieve the worker with the lowest hiring cost.
  • The selection process involves a sliding window approach where we add workers from both ends until we reach k hired workers.
  • Candidates can overlap between the two ends of the array, making careful indexing important.

Space and Time Complexity

Time Complexity: O(k log k)
Space Complexity: O(candidates)

Solution

To solve this problem, we utilize a min-heap (priority queue) to efficiently track the least expensive workers from both the beginning and the end of the costs array. We perform the following steps:

  1. Initialize a min-heap to keep track of the candidates from both the front and the back of the costs array.
  2. For each hiring session up to k, we:
    • Add the next available candidates from the front and back of the array to the heap.
    • Extract the worker with the lowest cost from the heap.
    • Add this cost to the total hiring cost and mark the worker as hired (remove them from consideration).
  3. Continue this process until we have hired k workers.

This approach ensures we always select the least expensive option available according to the hiring rules.

Code Solutions

import heapq

def totalCost(costs, k, candidates):
    n = len(costs)
    total_cost = 0
    min_heap = []

    left, right = 0, n - 1
    for _ in range(min(candidates, n)):
        if left <= right:
            heapq.heappush(min_heap, (costs[left], left))
            left += 1
        if left <= right:
            heapq.heappush(min_heap, (costs[right], right))
            right -= 1

    for _ in range(k):
        if min_heap:
            cost, idx = heapq.heappop(min_heap)
            total_cost += cost
            # Mark the worker as hired by not adding them back to the heap.
            if left <= right:
                if left <= right:
                    heapq.heappush(min_heap, (costs[left], left))
                    left += 1
                if left <= right:
                    heapq.heappush(min_heap, (costs[right], right))
                    right -= 1

    return total_cost
← Back to All Questions