Quick Overview

This question evaluates skill in array manipulation, data preprocessing, and algorithmic optimization for matching resources to tasks and aggregating profits.

Maximize Chef Assignment Profit

Company: DoorDash

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given three integer arrays: - `chefSkill[i]`: the skill level of the `i`-th chef. - `dishDifficulty[j]`: the difficulty level required to cook the `j`-th dish. - `dishProfit[j]`: the profit earned by cooking the `j`-th dish. Each chef can cook at most one dish. A chef can cook dish `j` only if `chefSkill[i] >= dishDifficulty[j]`. Multiple chefs are allowed to cook the same dish independently, and each cooking earns the full profit for that dish. Return the maximum total profit obtainable by assigning each chef to at most one dish. Example: ```text chefSkill = [1, 2, 3] dishDifficulty = [1, 2, 3] dishProfit = [1, 2, 3] ``` The maximum total profit is `1 + 2 + 3 = 6`. Follow-up: Suppose you want to build an array `bestProfitByDifficulty` where index `d` represents a difficulty level and `bestProfitByDifficulty[d]` stores the maximum profit of any dish that a chef with skill level `d` can cook. Given `dishDifficulty` and `dishProfit`, describe how you would generate this array.

Quick Answer: This question evaluates skill in array manipulation, data preprocessing, and algorithmic optimization for matching resources to tasks and aggregating profits.

Part 1: Maximum Total Profit from Chef Assignments

You are given three integer arrays: `chefSkill`, `dishDifficulty`, and `dishProfit`. A chef can cook at most one dish, and chef `i` can cook dish `j` only if `chefSkill[i] >= dishDifficulty[j]`. Multiple chefs are allowed to cook the same dish independently, and each chef earns the full profit of the dish they cook. Return the maximum total profit obtainable if each chef chooses the most profitable dish they can cook.

Constraints

  • 0 <= len(chefSkill) <= 100000
  • 0 <= len(dishDifficulty) == len(dishProfit) <= 100000
  • 0 <= chefSkill[i], dishDifficulty[j], dishProfit[j] <= 1000000000
  • The total profit may exceed 32-bit integer range.

Examples

Input: ([1, 2, 3], [1, 2, 3], [1, 2, 3])

Expected Output: 6

Explanation: Each chef can cook the dish with the matching difficulty, so the total is 1 + 2 + 3 = 6.

Input: ([5, 5, 5], [2, 4], [10, 50])

Expected Output: 150

Explanation: All three chefs can cook the difficulty-4 dish worth 50 profit, and the same dish can be reused.

Hints

  1. If you sort dishes by difficulty, you can track the best profit seen so far as difficulty increases.
  2. If you also sort the chefs by skill, you can scan through the dishes only once.

Part 2: Build Best Profit by Difficulty Array

You are given two integer arrays: `dishDifficulty` and `dishProfit`. Build and return an array `bestProfitByDifficulty` such that for every difficulty `d`, `bestProfitByDifficulty[d]` is the maximum profit of any dish with difficulty at most `d`. The returned array should cover every difficulty from `0` to `max(dishDifficulty)` inclusive. If there are no dishes, return `[0]`.

Constraints

  • 0 <= len(dishDifficulty) == len(dishProfit) <= 100000
  • 0 <= dishDifficulty[j] <= 200000
  • 0 <= dishProfit[j] <= 1000000000

Examples

Input: ([1, 2, 3], [1, 2, 3])

Expected Output: [0, 1, 2, 3]

Explanation: At each difficulty, the best available profit is the largest profit among dishes up to that difficulty.

Input: ([2, 4, 2, 5], [10, 20, 15, 5])

Expected Output: [0, 0, 15, 15, 20, 20]

Explanation: Difficulty 2 has two dishes, so keep the better profit 15. Then apply prefix maxima.

Hints

  1. First store the best profit for each exact difficulty value.
  2. Then sweep from left to right and turn the array into a prefix maximum array.

Loading coding console...