Luggage Cost With Purchases

HardPython

Problem

A Flexport itinerary has n destinations. At destination i, demand[i] bags must be transported on the next leg. Each bag can be covered by a purchased allowance or handled by paying the destination expense destination_fees[i].

An allowance offer is represented as [start, end, quantity, cost]. It provides up to quantity allowance units, each costing cost. A unit purchased from this offer can cover one bag on any destination index from start through end, inclusive, but it cannot be reused. You may purchase any amount up to an offer's quantity.

Return the minimum total cost needed to cover every bag. Every bag must be covered either by one allowance unit or by its destination expense.

Formal Specification

Implement min_luggage_cost(demand, destination_fees, offers).

demand and destination_fees are integer arrays of length n.
offers is an array of integer arrays [start, end, quantity, cost].
Return one integer, the minimum total cost.

Constraints

1 <= n <= 100
0 <= demand[i] <= 5000
0 <= destination_fees[i], cost <= 10^6
0 <= len(offers) <= 500
0 <= start <= end < n
1 <= quantity <= 5000
The answer fits in a signed 64-bit integer

Function Signature

def min_luggage_cost(demand, destination_fees, offers):

Return the minimum total cost needed to cover every bag. Every bag must be covered either by one allowance unit or by its destination expense.

Formal Specification

Implement min_luggage_cost(demand, destination_fees, offers).

demand and destination_fees are integer arrays of length n.
offers is an array of integer arrays [start, end, quantity, cost].
Return one integer, the minimum total cost.