Minimum cost to cut a board / chocolate into pieces
Problem
An m × n board must be cut into 1 × 1 squares. Each horizontal and vertical cut line has its own cost, and a cut's cost is multiplied by the number of pieces it passes through at that moment. Return the minimum total cost.
Example 1
Input: x (vertical) = [2, 1, 3, 1, 4], y (horizontal) = [4, 1, 2], board 6 × 4 Output: 42
Also asked as: Minimum Cost to cut a board into squares · CHOCOLA –Chocolate
Test cases
Case 1
Input: [4,1,2], [2,1,3,1,4] Expected: 42
Case 2
Input: [2], [1,3] Expected: 9
Case 3
Input: [1], [1] Expected: 3
Case 4
Input: [], [5] Expected: 5
View solutionHide solution1 approach
1. Sort all cut costs descending; a cut’s cost is multiplied by the current number of segments on the other axis
Time O(n log n)Space O(1)
Make expensive cuts first, while the perpendicular segment count is still low. Track how many horizontal and vertical pieces exist so far.
function minCutCost(horizontal, vertical) { horizontal.sort((a, b) => b - a); vertical.sort((a, b) => b - a); let hi = 0, vi = 0, hPieces = 1, vPieces = 1, cost = 0; while (hi < horizontal.length && vi < vertical.length) { if (horizontal[hi] >= vertical[vi]) { cost += horizontal[hi++] * vPieces; hPieces++; } else { cost += vertical[vi++] * hPieces; vPieces++; } } while (hi < horizontal.length) cost += horizontal[hi++] * vPieces; while (vi < vertical.length) cost += vertical[vi++] * hPieces; return cost;}