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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Tasks You Can Assign

Number: 2180

Difficulty: Hard

Paid? No

Companies: sabre, IBM, Walmart Labs

Problem Description

Given two arrays, tasks and workers, where each task has a minimum strength requirement and each worker has a current strength, determine the maximum number of tasks that can be completed. Each worker can perform at most one task if their strength is greater than or equal to the task's requirement. Additionally, you have a limited number of magical pills that can boost a worker's strength by a fixed value (each worker may receive at most one pill). The objective is to maximize the number of completed tasks by smartly assigning workers and pills.

Key Insights

  • Sort both tasks and workers to facilitate greedy matching.
  • Use binary search to determine the maximum number of tasks that can be assigned.
  • Develop a feasibility function that checks if x tasks can be fulfilled by pairing the x hardest tasks with x appropriate workers.
  • Greedily assign tasks: use a worker if they meet the requirement without a pill; otherwise, use a pill if available and effective.
  • The binary search narrows down the best achievable number of completed tasks.

Space and Time Complexity

Time Complexity: O(n log n + m log m + (n+m) log(min(n, m)))
Space Complexity: O(n + m)

Solution

The solution begins by sorting both the tasks and workers arrays. Then, we use binary search to decide the maximum number of tasks that can be assigned (x). For each candidate x, a feasibility check is performed where we try to match the x hardest tasks (the last x elements in tasks after sorting) with the x weakest workers that can be assigned (a subarray from workers). For each task, if the worker’s strength is enough, we assign the task directly; if not but a pill can boost the worker to the necessary level, we apply the pill (if available). If neither condition is met for any task, then x is not achievable. Adjusting the binary search bounds based on feasibility will find the maximum possible task assignment.

Code Solutions

# Python solution with line-by-line comments
def maxTaskAssign(tasks, workers, pills, strength):
    # Sort tasks and workers arrays to facilitate greedy matching.
    tasks.sort()
    workers.sort()

    # Helper function to check if x tasks can be assigned.
    def canAssign(x):
        usedPills = 0
        # Start from the worker index that gives us x available workers.
        worker = len(workers) - x  
        # Iterate over the x hardest tasks.
        for task in tasks[len(tasks) - x:]:
            # If the current worker meets the requirement without a pill, assign the task.
            if worker < len(workers) and workers[worker] >= task:
                worker += 1
            else:
                # If the worker cannot meet the requirement, try to use a pill.
                if usedPills < pills:
                    # Check if the boosted strength is sufficient.
                    if workers[worker] + strength < task:
                        return False
                    usedPills += 1
                    worker += 1
                else:
                    return False
        return True

    # Binary search for the maximum number of tasks that can be performed.
    lo, hi, result = 0, min(len(tasks), len(workers)), 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if canAssign(mid):
            result = mid  # mid tasks can be assigned, try for more.
            lo = mid + 1
        else:
            hi = mid - 1
    return result

# Example usage:
# tasks = [3, 2, 1]
# workers = [0, 3, 3]
# pills = 1
# strength = 1
# print(maxTaskAssign(tasks, workers, pills, strength))  # Expected output: 3
← Back to All Questions