Minimum Cost for Cutting Cake I
Problem
You have an m × n cake that must be sliced into 1 × 1 pieces. There are m - 1 horizontal lines and n - 1 vertical lines you may cut along, with prices horizontalCut[i] and verticalCut[j]. Each time you slice along a line, the cut runs across every piece currently sitting on that line, and you pay its price once for each of those pieces. Return the minimum total cost to cut the whole cake into unit squares.
m=3, n=2, horizontalCut=[1,3], verticalCut=[5]13def minimum_cost(m, n, horizontal_cut, vertical_cut):
cuts = [(c, "h") for c in horizontal_cut] + [(c, "v") for c in vertical_cut]
cuts.sort(reverse=True)
h_pieces, v_pieces = 1, 1
total = 0
for cost, kind in cuts:
if kind == "h":
total += cost * v_pieces
h_pieces += 1
else:
total += cost * h_pieces
v_pieces += 1
return totalfunction minimumCost(m, n, horizontalCut, verticalCut) {
const cuts = horizontalCut.map(c => [c, "h"])
.concat(verticalCut.map(c => [c, "v"]));
cuts.sort((a, b) => b[0] - a[0]);
let hPieces = 1, vPieces = 1, total = 0;
for (const [cost, kind] of cuts) {
if (kind === "h") { total += cost * vPieces; hPieces++; }
else { total += cost * hPieces; vPieces++; }
}
return total;
}class Solution {
public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
int[][] cuts = new int[m - 1 + n - 1][2];
int idx = 0;
for (int c : horizontalCut) cuts[idx++] = new int[]{ c, 0 };
for (int c : verticalCut) cuts[idx++] = new int[]{ c, 1 };
Arrays.sort(cuts, (a, b) -> b[0] - a[0]);
long hPieces = 1, vPieces = 1, total = 0;
for (int[] cut : cuts) {
if (cut[1] == 0) { total += (long) cut[0] * vPieces; hPieces++; }
else { total += (long) cut[0] * hPieces; vPieces++; }
}
return total;
}
}long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
vector<pair<int, int>> cuts;
for (int c : horizontalCut) cuts.push_back({ c, 0 });
for (int c : verticalCut) cuts.push_back({ c, 1 });
sort(cuts.rbegin(), cuts.rend());
long long hPieces = 1, vPieces = 1, total = 0;
for (auto& cut : cuts) {
if (cut.second == 0) { total += (long long) cut.first * vPieces; hPieces++; }
else { total += (long long) cut.first * hPieces; vPieces++; }
}
return total;
}Explanation
Every horizontal line eventually gets cut, and every vertical line eventually gets cut — there is no choice about whether to cut, only about the order. So the question is really: in what order do we make the cuts to keep the total cheap?
Here is the key observation. When you slice along a horizontal line, the blade runs across the full width of the cake and pays its price once for every column the cake is currently split into. If you have already made v vertical cuts, the cake has v + 1 columns, so that one horizontal cut costs price × (v + 1). Symmetrically, a vertical cut costs price × (h + 1) where h is the number of horizontal cuts done so far.
That multiplier only grows as you keep cutting — it never shrinks. So an expensive cut is cheapest to make early, while the cake is still in few pieces, and a cheap cut barely hurts even if its multiplier has grown large. The greedy rule falls right out: always perform the most expensive remaining cut next, regardless of whether it is horizontal or vertical.
Concretely, throw all the prices into one list, sort it from highest to lowest, and walk it. Track how many horizontal pieces (h_pieces) and vertical pieces (v_pieces) currently exist — both start at 1. A horizontal cut adds cost × v_pieces and then bumps h_pieces; a vertical cut adds cost × h_pieces and bumps v_pieces.
Trace the example m=3, n=2, horizontalCut=[1,3], verticalCut=[5]. Sorted prices are 5(v), 3(h), 1(h). The vertical 5 costs 5×1 = 5 (one row so far). Now 2 columns exist, so the horizontal 3 costs 3×2 = 6 and the horizontal 1 costs 1×2 = 2. Total 5 + 6 + 2 = 13, matching the expected answer.