. La plupart des travaux d'affectation des bénéfices

826. La plupart des travaux d'affectation des bénéfices

Moyen

Vous avez n emplois et m travailleurs. Vous disposez de trois tableaux : difficulté, profit et travailleur où :

• difficulté[i] et profit[i] sont la difficulté et le profit du i^ème travail, et
• travailleur[j] est la capacité du j^ème travailleur (c'est-à-dire que le j^ème travailleur ne peut terminer un travail qu'avec difficulté au plus travailleur[j]).

Chaque travailleur peut se voir attribuer au plus une tâche, mais une tâche peut être réalisée plusieurs fois.

• Par exemple, si trois travailleurs tentent le même travail qui rapporte 1 $, le bénéfice total sera de 3 $. Si un travailleur ne peut terminer aucun travail, son bénéfice est de 0 $.

Rendre le profit maximum que nous pouvons réaliser après avoir affecté les travailleurs aux emplois.

Exemple 1 :

• Entrée : difficulté = [2,4,6,8,10], profit = [10,20,30,40,50], travailleur = [4,5,6,7]
• Sortie : 100
• Explication : Les travailleurs se voient attribuer des tâches difficiles [4,4,6,6] et obtiennent un bénéfice de [20,20,30,30] séparément.

Exemple 2 :

• Entrée : difficulté = [85,47,57], profit = [24,66,99], travailleur = [40,25,25]
• Sortie : 0

Contraintes :

• n == difficulté.longueur
• n == profit.length
• m == travailleur.longueur
• 1 <= n, m <= 10⁴
• 1 <= difficulté[i], profit[i], travailleur[i] <= 10⁵

Solution :

class Solution {

    /**
     * @param Integer[] $difficulty
     * @param Integer[] $profit
     * @param Integer[] $worker
     * @return Integer
     */
    function maxProfitAssignment($difficulty, $profit, $worker) {
        $ans = 0;
        $jobs = array();

        for ($i = 0; $i < count($difficulty); ++$i) {
            $jobs[] = array($difficulty[$i], $profit[$i]);
        }

        sort($jobs);
        sort($worker);

        $i = 0;
        $maxProfit = 0;

        foreach ($worker as $w) {
            for (; $i < count($jobs) && $w >= $jobs[$i][0]; ++$i) {
                $maxProfit = max($maxProfit, $jobs[$i][1]);
            }
            $ans += $maxProfit;
        }

        return $ans;
    }
}




Liens de contact


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!