🌟Today's hub daily🌟
826. Most Profit Assigning Work
❔ Problem: Given n jobs, m workers, and three arrays: difficulty, profit, and worker:
difficulty[i] and profit[i] are the difficulty and profit of the i-th job.
worker[j] is the max difficulty the j-th worker can work.
Each worker can be assigned at most one job, but a job can be completed multiple times. we need to return the maximum profit we can achieve after assigning the workers to the jobs. 👨💼🧑💼
➡️ Approach:
Map Profit to Minimum Difficulty: Create a dictionary mapping each profit to the minimum difficulty required to achieve it.
Sort Workers: Sort the worker array in descending order. s
Use a Max Heap: Convert the profit array into a max heap (by using negative values).
Calculate Total Profit: Iterate over the workers and calculate the total profit they can achieve based on their abilities(by heappopping the maximum profit and assigning it to the the ith worker...since the workers are sorted in descending order of their ability, we're guarreteed of not missing out an opportunity to assign high profitable job to the cabable worker)
📊 Time complexity: O(nlogn + mlogm) the sorting part and the heap operation
📂 Space complexity:O(n)... the dictionary
https://leetcode.com/problems/most-profit-assigning-work/ #Leetcode #DailyChallenge #Heap #Sorting
