thảo luận Leetcode mỗi ngày

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        worker, jobs = sorted(worker), sorted(zip(difficulty, profit))
        n, profits, maxSofar, current = len(jobs), 0, 0, 0
        for i in range(len(worker)):
            while current < n and worker[i] >= jobs[current][0]:
                maxSofar = max(maxSofar, jobs[current][1])
                current += 1
            profits += maxSofar
                
        return profits

function maxProfitAssignment(d: number[], p: number[], w: number[]): number {
    const arr: number[][] = [];
    for (let i = 0; i < d.length; i++) {
        arr.push([d[i], p[i]]);
    }
    arr.sort((a, b) => a[0] - b[0]);
    for (let i = 0; i < arr.length - 1; i++) {
        arr[i+1][1] = Math.max(arr[i][1], arr[i+1][1])
    }
    let res = 0;
    for (const num of w) {
        if (num < arr[0][0]) continue;
        let l = 0, r = arr.length - 1, p = 0;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
            if (arr[m][0] <= num) {
                p = Math.max(p, arr[m][1]);
                l = m + 1
            } else r = m -1;
        }
        res+= p;
    }
    return res;
};

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        d_pro = [(d,p) for d,p in zip(difficulty, profit)]
        d_pro.sort()
        worker.sort()
        ans, i, profit = 0,0, 0
        for w in worker:
            while i < len(d_pro) and d_pro[i][0] <= w:
                profit = max(profit, d_pro[i][1])
                i += 1
            ans += profit
        return ans

class Solution {

    /**
     * @param Integer[] $difficulty
     * @param Integer[] $profit
     * @param Integer[] $worker
     * @return Integer
     */
    function maxProfitAssignment($difficulty, $profit, $worker) {
        sort($worker);
        $maxAbility = $worker[count($worker)-1];

        // creat hash table
        $profitDiff = [];
        foreach ($difficulty as $i => $d) {
            if ($d > $maxAbility) {
                continue;
            }

            $p = $profit[$i];
            if (isset($profitDiff[$p])) {
                // only get highest profit with smallest difficulty
                $profitDiff[$p] = ($profitDiff[$p] > $difficulty[$i]) ? $difficulty[$i] : $profitDiff[$p];
                continue;
            }

            $profitDiff[$p] = $difficulty[$i];
        }

        // if it has no jobs after filter => return 0
        if (!count($profitDiff)) return 0;
        ksort($profitDiff);
 
        // calculate max profit
        $maxProfit = 0;
        end($profitDiff);
        $posibleProfit = key($profitDiff);
        $diff = array_pop($profitDiff);
        $ability = array_pop($worker);
        while (true) {
            if ($diff <= $ability) {
                $maxProfit += $posibleProfit;

                if (!count($worker)) return $maxProfit;
                $ability = array_pop($worker);
            } else {
                if (!count($profitDiff)) return $maxProfit;

                end($profitDiff);
                $posibleProfit = key($profitDiff);
                $diff = array_pop($profitDiff);
            }
        }
    }
}

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        n = len(difficulty)
        jobs = sorted([(profit[i], difficulty[i]) for i in range(n)], reverse=True)
        worker.sort(reverse=True)
        result, i = 0, 0

        for w in worker:
            while i < n and jobs[i][1] > w:
                i += 1
            if i >= n:
                break
            result += jobs[i][0]
        return result

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit,
                            vector<int>& worker) {
        vector<pair<int, int>> projects;
        for (int i = 0; i < profit.size(); i++) {
            projects.push_back(make_pair(difficulty[i], profit[i]));
        }
        sort(projects.begin(), projects.end());
        sort(worker.begin(), worker.end());

        int maxProfit {0};
        int j{0};
        int result{0};

        for(int i = 0; i < worker.size(); i++){
            while(j < projects.size() && projects[j].first <= worker[i]){
                maxProfit = std::max(maxProfit, projects[j].second);
                ++j;
            }
            result += maxProfit;
        }
        return result;
    }
};

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = profit.length;
        int[][] job=new int[n][2];
        for(int i =0;i<n;i++){
            job[i][0]= difficulty[i];
            job[i][1] = profit[i];
        }
        int res =0;
        Arrays.sort(job, Comparator.<int[]>comparingInt(x -> x[0]));
        Arrays.sort(worker);
        int curJob = 0;
        int maxProfit=0;
        for(int i = 0;i<worker.length;i++){
            while(curJob < n &&  worker[i] >= job[curJob][0]){
                maxProfit = Math.max(maxProfit,job[curJob][1]);
                curJob++;
            }
            res+=maxProfit;
        }
       
        return res;
    }
}

public class Solution {
    public int MaxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        PriorityQueue<(int, int), int> pq = new PriorityQueue<(int, int), int>();
        for(int i = 0; i<profit.Length;i++)
        {
            pq.Enqueue((difficulty[i], profit[i]), -profit[i]);
        }
        Array.Sort(worker, (a,b) => b.CompareTo(a));
        int index = 0;
        int result = 0;
        while(pq.Count > 0 && index < worker.Length)
        {
            var item = pq.Dequeue();
            while(index < worker.Length && worker[index] >= item.Item1)
            {
                result += item.Item2;
                index++;
            }
        }
        return result;
    }
}

class Solution {
public:
    int maxProfitAssignment(vector<int> const& difficulty, vector<int> const& profit, vector<int>& worker) {
        int np = profit.size(), nw = worker.size(), res = 0, current_max_profit = 0, t = 0;
        vector<int> idx(np, 0);
        for (int i = 1; i < np; ++i) idx[i] = i;
        sort(begin(idx), end(idx), [&](int i, int j) { return difficulty[i] < difficulty[j]; });
        sort(begin(worker), end(worker));
        
        for (auto w : worker) {
            while (t < np && difficulty[idx[t]] <= w)
                current_max_profit = max(current_max_profit, profit[idx[t++]]);
            res += current_max_profit;
        }
        return res;
    }
};

class Solution {
    func maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {

        let combined = zip(difficulty, profit).sorted {$0.0 < $1.0}

        var result = 0
        for w in worker {
            var maxProfit = 0
            var index = 0
            while index < combined.count {
                let combine = combined[index]
                if combine.0 > w {
                    break
                }
                if combine.1 > maxProfit {
                    maxProfit = combine.1
                }
                index += 1
            }
            result += maxProfit
        }
        return result
    }
}

class Solution {
class Solution {
    func maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {
        let combined = zip(difficulty, profit).sorted {$0.0 < $1.0}
        let worker = worker.sorted()
        var result = 0
        var lastIndex = 0
        var lastMaxProfit = 0
        for w in worker {
            var maxProfit = lastMaxProfit
            var index = lastIndex
            while index < combined.count {
                let combine = combined[index]
                if combine.0 > w {
                    break
                } 
                if combine.1 > maxProfit {
                    maxProfit = combine.1
                }
                index += 1
            }
            lastIndex = index
            lastMaxProfit = maxProfit
            result += maxProfit
        }
        return result
    }
}
}

object Solution {
    def maxProfitAssignment(difficulty: Array[Int], profit: Array[Int], worker: Array[Int]): Int = {
    val jobs = difficulty.zip(profit).sortBy(_._1)
    
    val sortedWorkers = worker.sorted
    
    var maxProfit = 0
    var best = 0
    var jobIndex = 0
    
    for (w <- sortedWorkers) {
      while (jobIndex < jobs.length && jobs(jobIndex)._1 <= w) {
        best = Math.max(best, jobs(jobIndex)._2)
        jobIndex += 1
      }
      maxProfit += best
    }
    
    maxProfit
  }
}

use std::collections::*;
impl Solution {
    pub fn max_profit_assignment(difficulty: Vec<i32>, profit: Vec<i32>, worker: Vec<i32>) -> i32 {
        // dedup, keep only the task with the max profit if there are multiple tasks with the same difficulty
        let mut task_map: HashMap<i32, i32> =
            difficulty.into_iter().zip(profit.into_iter()).
                fold(HashMap::new(), |mut acc, (diff, prof)| {
                    acc.entry(diff).
                        and_modify(|stored_prof| *stored_prof = (*stored_prof).max(prof)).
                        or_insert(prof);
                    acc
                });

        // (diff, prof)
        let mut tasks: Vec<(i32, i32)> = task_map.into_iter().collect();

        // sort by difficulty
        tasks.sort_unstable_by_key(|pair| pair.0);

        // find max profit for each prefix
        let mut max_profit = tasks[0].1;
        for i in (1..(tasks.len())) {
            max_profit = max_profit.max(tasks[i].1);
            tasks[i].1 = max_profit;
        }

        let mut total_profit = 0;
        for j in 0..(worker.len()) {
            // if we can assign a worker a task at the index `i`, then we can also assign that worker
            // any tasks in the prefix tasks[0..=i] as we sorted the tasks by difficulty
            // thus we can pick the task in the prefix tasks[0..=i] with the highest profit
            // here binary search is used to find the max possible `i` for each worker
            let task_index_result =
                tasks.binary_search_by(|pair| pair.0.cmp(&worker[j]));

            match task_index_result {
                Ok(i) => total_profit += tasks[i].1,
                Err(i) => {
                    if i > 0 {
                        total_profit += tasks[i - 1].1;
                    }
                }
            }
        }
        total_profit
    }
}