FastPrep
Problem · Greedy

Maximize Total Profit by Assigning Chefs to Dishes

Learn this problem
● MediumDoorDash logoDoorDashFULLTIMEPHONE SCREEN

Problem statement

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

solveMaximizeChefDishProfit(input: String) → String[]

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

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