Minimum cost to cut a board / chocolate into pieces

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}