Introduction

In this blog post, we will explore how to solve the LeetCode problem "826" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where: difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]). Every worker can be assigned at most one job, but one job can be completed multiple times. For example, if three workers attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, their profit is $0. Return the maximum profit we can achieve after assigning the workers to the jobs. Example 1: Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7] Output: 100 Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately. Example 2: Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25] Output: 0 Constraints: n == difficulty.length n == profit.length m == worker.length 1 <= n, m <= 104 1 <= difficulty[i], profit[i], worker[i] <= 105

Explanation

Here's the breakdown of the solution:

• Sort Jobs by Difficulty: Sort the jobs based on their difficulty in ascending order. This allows us to efficiently iterate through the jobs that a worker is capable of doing. Simultaneously, keep track of the maximum profit achievable for each difficulty level encountered so far.

• Sort Workers by Ability: Sort the workers based on their ability in ascending order. This allows us to process workers in increasing order of capability, maximizing their potential profit.

• Greedy Assignment: Iterate through the sorted workers. For each worker, find the maximum profit they can achieve from the jobs they are capable of doing (determined using the sorted jobs). Add this profit to the total profit.

• Runtime & Storage Complexity: O(n log n + m log m), where n is the number of jobs and m is the number of workers. The dominant factor is the sorting of jobs and workers. Storage complexity is O(n), primarily due to the sorted job data.

Code

    def max_profit_assignment(difficulty: list[int], profit: list[int], worker: list[int]) -> int:
    """
    Calculates the maximum profit achievable by assigning workers to jobs based on their ability.

    Args:
        difficulty (list[int]): The difficulty of each job.
        profit (list[int]): The profit of each job.
        worker (list[int]): The ability of each worker.

    Returns:
        int: The maximum profit achievable.
    """
    jobs = sorted(zip(difficulty, profit))  # Sort jobs by difficulty
    worker.sort()  # Sort workers by ability

    max_profit_so_far = 0
    job_index = 0
    total_profit = 0

    for worker_ability in worker:
        # Find the maximum profit a worker can achieve
        while job_index < len(jobs) and jobs[job_index][0] <= worker_ability:
            max_profit_so_far = max(max_profit_so_far, jobs[job_index][1])
            job_index += 1
        total_profit += max_profit_so_far  # Accumulate the profit

    return total_profit