Frontend School

Delivery Partner Earnings Maximizer

DSA
hard

Delivery Partner Earnings Maximizer

Hard
Dynamic Programming
Knapsack
Multi-dimensional DP

Overview

As a Swiggy delivery partner, optimizing your time and earnings is crucial. Imagine you've arrived at a restaurant, and there are multiple ready-to-pickup orders. Each order has a specific preparation time (even if ready, there's a small handover/packaging time) and an associated earning (delivery fee + potential tip). You have a limited amount of time you can afford to spend at this particular restaurant before it impacts your overall delivery schedule. Additionally, your delivery bag has a limited capacity, meaning you can only carry a certain number of orders at once. Your goal is to select a subset of available orders to maximize your total earnings while respecting both the maximum wait time and the maximum number of orders you can carry.

What you need to do / Task

Implement a function maximizeEarnings that takes the following parameters:

  1. prepTimes: An array of integers where prepTimes[i] is the time (in minutes) required for the i-th order.
  2. earnings: An array of integers where earnings[i] is the earning (in rupees) for the i-th order.
  3. maxWaitTime: An integer representing the maximum total time (in minutes) you can spend at the restaurant.
  4. maxOrdersToCarry: An integer representing the maximum number of orders you can pick up.

The function should return the maximum total earnings achievable.

Input & Output

Function Signature: function maximizeEarnings(prepTimes: number[], earnings: number[], maxWaitTime: number, maxOrdersToCarry: number): number

Parameters:

  • prepTimes: An array of N positive integers representing the preparation/handover time for each order.
  • earnings: An array of N positive integers representing the earnings for each order.
  • maxWaitTime: A positive integer representing the maximum total time budget.
  • maxOrdersToCarry: A positive integer representing the maximum number of orders that can be picked up.

Return Value:

  • A single non-negative integer representing the maximum total earnings. If no orders can be picked while satisfying constraints, return 0.

Clarifications

  • All orders are distinct and can only be picked once (0/1 choice).
  • The prepTimes and earnings arrays will always have the same length, N.
  • You must select a subset of orders. You cannot pick fractional orders.
  • If it's impossible to pick any orders within the given constraints, the maximum earnings should be 0.

Examples

1

Example 1

Input:

prepTimes = [10, 20, 30], earnings = [60, 100, 120], maxWaitTime = 50, maxOrdersToCarry = 2

Output:

220

Note:

To maximize earnings, pick orders with (time=20, earn=100) and (time=30, earn=120). Total time = 50 (<= maxWaitTime), total orders = 2 (<= maxOrdersToCarry). Total earnings = 220.

2

Example 2

Input:

prepTimes = [5, 5, 5], earnings = [10, 20, 30], maxWaitTime = 10, maxOrdersToCarry = 1

Output:

30

Note:

With maxOrdersToCarry = 1, you can only pick one order. The order with (time=5, earn=30) yields the highest earnings while respecting maxWaitTime.

3

Example 3

Input:

prepTimes = [100, 150], earnings = [200, 300], maxWaitTime = 50, maxOrdersToCarry = 1

Output:

0

Note:

Neither order can be picked as their individual preparation times (100 and 150) exceed the maxWaitTime of 50. No orders can be picked, so earnings are 0.

Constraints

Constraints & assumptions

  • 1 <= N <= 200 (where N is the number of available orders)
  • 1 <= prepTimes[i] <= 100 for all i
  • 1 <= earnings[i] <= 500 for all i
  • 1 <= maxWaitTime <= 2000
  • 1 <= maxOrdersToCarry <= N
  • maxOrdersToCarry <= 20
  • All input values are positive integers.

Out of scope

  • Handling negative input values or non-integer inputs.
  • Optimizing for scenarios where N is extremely large (e.g., millions of orders).
  • Considering the geographical location or delivery route optimization for these orders.

What interviewers evaluate

  • Algorithmic Correctness: The solution must correctly identify the maximum earnings under all given constraints.
  • Efficiency: The solution should be optimally efficient in terms of time and space complexity for the given constraints.
  • Problem Decomposition & DP State: Ability to break down the problem into subproblems and define an appropriate dynamic programming state.
  • Edge Case Handling: Correctly handles scenarios like no orders fitting the constraints or when constraints are very tight.
  • Code Quality: Clear, well-structured, and readable code with appropriate variable names.

Loading editor...