FastPrep
Problem · Greedy

Maximize Total Profit by Assigning Chefs to Dishes

● MediumDoorDashFULLTIMEPHONE SCREEN

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

You are given three integer arrays:

  • chefSkill: each chef's skill level
  • dishDifficulty: each dish's difficulty
  • dishProfit: the profit earned for completing that dish

Rules:

  • Each chef can complete at most one dish.
  • A dish can be completed by multiple chefs (dishes are not exclusive).
  • A chef can only complete a dish if dishDifficulty[i] <= chefSkill[j].
  • Each chef independently picks the most profitable dish they are able to complete.
  • If a chef cannot complete any dish, they contribute 0 profit.

Compute the maximum total profit by assigning each chef the best dish they can do.

Input Format:

  • Line 1: integer n — number of chefs
  • Line 2: n space-separated integers — chefSkill
  • Line 3: integer m — number of dishes
  • Line 4: m space-separated integers — dishDifficulty
  • Line 5: m space-separated integers — dishProfit

Output Format:

A single integer: the maximum total profit.

Example

Input:

3
1 2 3
3
1 2 3
1 2 3

Output:

6

Explanation: Chef with skill 1 picks dish with difficulty 1 (profit 1). Chef with skill 2 picks dish with difficulty 2 (profit 2). Chef with skill 3 picks dish with difficulty 3 (profit 3). Total = 6.

Task

Return the maximum total profit as an integer.

Function Description

Complete solveMaximizeChefDishProfit. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Examples
01 · Example 1
input = "3\n1 2 3\n3\n1 2 3\n1 2 3"
return = ["6"]
Input has 5 lines: n=3, chefSkill=[1,2,3], m=3, dishDifficulty=[1,2,3], dishProfit=[1,2,3]. Each chef picks the most profitable dish whose difficulty does not exceed their skill: chef skill 1 → dish difficulty 1 profit 1; chef skill 2 → dish difficulty 2 profit 2; chef skill 3 → dish difficulty 3 profit 3. Total profit = 1 + 2 + 3 = 6.
Constraints
  • 1 <= n, m <= 2 * 105
  • dishDifficulty and dishProfit always have the same length m.
  • All skill, difficulty, and profit values are non-negative integers.
  • Arrays may be unsorted.
  • If a chef's skill is less than all dish difficulties, that chef contributes 0 to the total profit.
More DoorDash problems
drafts saved locally
public String[] solveMaximizeChefDishProfit(String input) {
    // write your code here
}
input"3\n1 2 3\n3\n1 2 3\n1 2 3"
expected["6"]
checking account