3789. Minimum Cost to Acquire Required Items
- Math
- Greedy
Intuition
Only the number of type 3 items matters. Once that number k is fixed, the rest is forced: buy type 1 items for whatever of need1 is still missing, and type 2 items for whatever of need2 is still missing. So the cost is a function of one variable:
f(k) = k * costBoth + max(0, need1 - k) * cost1 + max(0, need2 - k) * cost2
Every term is linear or a max(0, linear), so f is convex and piecewise linear. Its slope only changes at k = need1 and k = need2, and going past max(need1, need2) only adds cost. A convex piecewise linear function on an interval reaches its minimum at an endpoint or a breakpoint.
Approach
- Let
lo = min(need1, need2)andhi = max(need1, need2). - Evaluate
f(0),f(lo)andf(hi). - Return the smallest.
In greedy terms, f(lo) beats f(0) when costBoth < cost1 + cost2. Then f(hi) beats f(lo) when costBoth is also cheaper than the single-type item still needed for the leftover. Taking the min of the three covers all of these cases without branching.
Complexity
- Time: O(1)
- Space: O(1)
Edge Cases
need1 = need2 = 0: every candidate isf(0) = 0- One need is 0:
lo = 0, so the choice is between buying no type 3 items and covering everything with them costBothcheaper than one single item (example 1): type 3 items also cover the leftover of the larger need, sok = hicostBoth >= cost1 + cost2(example 2): never buy type 3, sok = 0- The answer can reach about
10^9 * 2 * 10^6 = 2 * 10^15, so Java must uselongfor every product
Code
class Solution:
def minimumCost(self, cost1: int, cost2: int, costBoth: int, need1: int, need2: int) -> int:
"""
3789. Minimum Cost to Acquire Required Items
Time: O(1)
Space: O(1)
"""
def total(k: int) -> int:
# Buy k type 3 items, then fill each remaining need with single items.
return k * costBoth + max(0, need1 - k) * cost1 + max(0, need2 - k) * cost2
# total(k) is convex and piecewise linear with breakpoints at need1 and
# need2, so the minimum is at 0 or one of those breakpoints.
return min(total(0), total(min(need1, need2)), total(max(need1, need2)))/**
* 3789. Minimum Cost to Acquire Required Items
* Time: O(1)
* Space: O(1)
*/
class Solution {
public long minimumCost(int cost1, int cost2, int costBoth, int need1, int need2) {
// total(k) is convex and piecewise linear with breakpoints at need1 and
// need2, so the minimum is at 0 or one of those breakpoints.
long lo = Math.min(need1, need2), hi = Math.max(need1, need2);
return Math.min(total(0, cost1, cost2, costBoth, need1, need2),
Math.min(total(lo, cost1, cost2, costBoth, need1, need2),
total(hi, cost1, cost2, costBoth, need1, need2)));
}
// Buy k type 3 items, then fill each remaining need with single items.
private long total(long k, long cost1, long cost2, long costBoth, long need1, long need2) {
return k * costBoth + Math.max(0, need1 - k) * cost1 + Math.max(0, need2 - k) * cost2;
}
}