Maximize Concurrent Order Profit
Meesho's logistics operations are critical for timely deliveries and profitability. This problem focuses on optimizing the selection of orders for fulfillment, aiming to maximize total profit under a strict constraint: the total concurrent capacity utilized by active orders must never exceed a given limit. This scenario is common in real-world resource allocation problems, from managing delivery fleets to cloud computing resources.
Implement a function maximizeConcurrentOrderProfit that, given a list of orders and a total available capacity, calculates the maximum total profit achievable by fulfilling a subset of these orders.
maximizeConcurrentOrderProfit function.Function Signature:
function maximizeConcurrentOrderProfit(orders: number[][], totalCapacity: number): number
Input:
orders: number[][]
An array where each inner array [startTime, endTime, capacityNeeded, profit] represents an order:
startTime: The time when the order is picked up and starts consuming capacity.endTime: The time when the order is delivered and frees up its consumed capacity. (The order is active during [startTime, endTime)).capacityNeeded: The amount of capacity this order consumes while active.profit: The profit generated if this order is fulfilled.totalCapacity: number
The maximum concurrent capacity available across all active orders at any given time.Output:
number: The maximum total profit achievable.[startTime, endTime). This means capacity is consumed at startTime and freed just before endTime.startTime, endTime, capacityNeeded, and profit values are non-negative integers.startTime < endTime for all orders.Examples
Example 1
Input:
orders = [[0, 5, 2, 10], [1, 6, 3, 12], [4, 7, 1, 5]], totalCapacity = 3
Output:
12
Note:
Order 0 (profit 10, cap 2) is taken. At time 1, Order 1 (profit 12, cap 3) arrives. Since it's more profitable than active Order 0, Order 0 is evicted to make space, and Order 1 is taken. At time 4, Order 2 (profit 5, cap 1) arrives, but capacity is full (3/3) and Order 2 is less profitable than active Order 1. So Order 2 is skipped. Total profit: 12.
Example 2
Input:
orders = [[0, 2, 1, 5], [1, 3, 1, 8], [2, 4, 1, 10]], totalCapacity = 3
Output:
23
Note:
All orders can be taken as their combined capacity never exceeds 3. Total profit = 5 + 8 + 10 = 23.
Example 3
Input:
orders = [[0, 10, 5, 100]], totalCapacity = 2
Output:
0
Note:
The only order requires 5 capacity, but total available capacity is 2. The order cannot be taken, resulting in 0 profit.
Example 4
Input:
orders = [[0, 2, 1, 10], [0, 2, 1, 12], [0, 1, 1, 5]], totalCapacity = 2
Output:
22
Note:
At time 0, Order 0 (profit 10, cap 1) is taken. Capacity 1/2. Order 1 (profit 12, cap 1) is also taken. Capacity 2/2. Order 2 (profit 5, cap 1) cannot be taken as capacity is full and it's less profitable than active orders. Order 2 ends at time 1, but was never taken. Orders 0 and 1 end at time 2. Total profit: 10 + 12 = 22.
Constraints
1 <= orders.length <= 10^50 <= startTime < endTime <= 10^91 <= capacityNeeded <= 10^91 <= profit <= 10^91 <= totalCapacity <= 10^9capacityNeeded for all orders can significantly exceed totalCapacity.Number type).O(N log N) time and O(N) space.Loading editor...