GreedyProblem 12 of 35
Minimum Cost to cut a board into squares
Problem Statement
Given a board of dimensions m x n with costs to cut along each horizontal and vertical line, find the minimum total cost to cut the board into unit squares (1x1 pieces).
Each cut costs are given as:
horizontal_cost[i]= cost to cut along horizontal line ivertical_cost[j]= cost to cut along vertical line j
When a cut is made, it goes through all pieces that line crosses. So if a board is already cut into pieces, the cost is multiplied by the number of pieces the cut passes through.
Constraints:
- 1 ≤ m, n ≤ 10^5
- 1 ≤ cost[i] ≤ 10^6
Example:
- Input:
m = 6, n = 4,horizontal_cost = [2, 1, 3, 1, 4],vertical_cost = [4, 1, 2] - Output:
42
Approach 1: Brute Force (Try All Orderings)
Intuition
Try all possible orderings of horizontal and vertical cuts. For each ordering, calculate the total cost considering piece multiplication.
Algorithm
- Generate all permutations of cut orderings
- For each ordering, simulate the cutting process
- Track number of horizontal and vertical pieces
- Calculate total cost
java
import java.util.*;
public class Solution {
private int minCost = Integer.MAX_VALUE;
private void tryAllOrders(int[][] cuts, int idx, int hPieces, int vPieces, int cost) {
if (idx == cuts.length) {
minCost = Math.min(minCost, cost);
return;
}
for (int i = idx; i < cuts.length; i++) {
int[] temp = cuts[idx];
cuts[idx] = cuts[i];
cuts[i] = temp;
int cutCost = cuts[idx][0];
int type = cuts[idx][1]; // 0 = H, 1 = V
if (type == 0) {
tryAllOrders(cuts, idx + 1, hPieces + 1, vPieces,
cost + cutCost * vPieces);
} else {
tryAllOrders(cuts, idx + 1, hPieces, vPieces + 1,
cost + cutCost * hPieces);
}
temp = cuts[idx];
cuts[idx] = cuts[i];
cuts[i] = temp;
}
}
public int minimumCost(int[] horizontalCost, int[] verticalCost) {
int total = horizontalCost.length + verticalCost.length;
int[][] cuts = new int[total][2];
int idx = 0;
for (int c : horizontalCost) {
cuts[idx++] = new int[]{c, 0};
}
for (int c : verticalCost) {
cuts[idx++] = new int[]{c, 1};
}
minCost = Integer.MAX_VALUE;
tryAllOrders(cuts, 0, 1, 1, 0);
return minCost;
}
}Complexity Analysis
- Time Complexity: O((m+n)! * (m+n)) - All permutations
- Space Complexity: O(m+n) - Recursion stack
Approach 2: Greedy (Cut Expensive Lines First) - Optimal
Intuition
To minimize total cost, make expensive cuts early when there are fewer pieces. Expensive cuts should be done first because their cost gets multiplied by fewer pieces.
Key Insight: If we cut the most expensive line first (whether horizontal or vertical), it passes through the minimum number of pieces.
Algorithm
- Sort horizontal costs in descending order
- Sort vertical costs in descending order
- Use two pointers to always pick the larger cost
- When making a horizontal cut, multiply by number of vertical pieces
- When making a vertical cut, multiply by number of horizontal pieces
java
import java.util.*;
public class BoardCutting {
public long minimumCost(int[] horizontalCost, int[] verticalCost) {
// Sort in descending order
Integer[] hCosts = Arrays.stream(horizontalCost).boxed().toArray(Integer[]::new);
Integer[] vCosts = Arrays.stream(verticalCost).boxed().toArray(Integer[]::new);
Arrays.sort(hCosts, Collections.reverseOrder());
Arrays.sort(vCosts, Collections.reverseOrder());
int hPieces = 1;
int vPieces = 1;
int h = 0, v = 0;
long totalCost = 0;
while (h < hCosts.length && v < vCosts.length) {
if (hCosts[h] >= vCosts[v]) {
totalCost += (long) hCosts[h] * vPieces;
hPieces++;
h++;
} else {
totalCost += (long) vCosts[v] * hPieces;
vPieces++;
v++;
}
}
while (h < hCosts.length) {
totalCost += (long) hCosts[h] * vPieces;
h++;
}
while (v < vCosts.length) {
totalCost += (long) vCosts[v] * hPieces;
v++;
}
return totalCost;
}
public static void main(String[] args) {
BoardCutting bc = new BoardCutting();
int[] horizontal = {2, 1, 3, 1, 4};
int[] vertical = {4, 1, 2};
System.out.println("Minimum cost: " + bc.minimumCost(horizontal, vertical));
}
}Dry Run Example
Board: 6 x 4 (needs 5 horizontal cuts, 3 vertical cuts)
horizontal_cost = [2, 1, 3, 1, 4]
vertical_cost = [4, 1, 2]
After sorting (descending):
h_costs = [4, 3, 2, 1, 1]
v_costs = [4, 2, 1]
Initial: h_pieces=1, v_pieces=1
Step 1: h_costs[0]=4 >= v_costs[0]=4
- Horizontal cut: cost = 4 × 1 = 4
- h_pieces = 2, total = 4
Step 2: h_costs[1]=3 < v_costs[0]=4
- Vertical cut: cost = 4 × 2 = 8
- v_pieces = 2, total = 12
Step 3: h_costs[1]=3 >= v_costs[1]=2
- Horizontal cut: cost = 3 × 2 = 6
- h_pieces = 3, total = 18
Step 4: h_costs[2]=2 >= v_costs[1]=2
- Horizontal cut: cost = 2 × 2 = 4
- h_pieces = 4, total = 22
Step 5: h_costs[3]=1 < v_costs[1]=2
- Vertical cut: cost = 2 × 4 = 8
- v_pieces = 3, total = 30
Step 6: h_costs[3]=1 >= v_costs[2]=1
- Horizontal cut: cost = 1 × 3 = 3
- h_pieces = 5, total = 33
Step 7: h_costs[4]=1 >= (no more v_costs)
- Horizontal cut: cost = 1 × 3 = 3
- total = 36
Step 8: (no more h_costs) v_costs[2]=1
- Vertical cut: cost = 1 × 6 = 6
- total = 42
Result: Minimum cost = 42
Why Greedy Works
Proof:
- Consider any two adjacent cuts in optimal order
- If a cheaper cut comes before expensive cut, swapping them reduces total cost
- Therefore, expensive cuts should always come first
- This is true for both horizontal and vertical cuts independently
Complexity Analysis
- Time Complexity: O((m+n) log(m+n)) - Dominated by sorting
- Space Complexity: O(m+n) for sorted arrays (or O(1) if sorting in place)
Key Takeaways
- Greedy by Cost: Always make the most expensive cut first
- Piece Multiplication: Cost is multiplied by number of pieces cut passes through
- Two Types of Cuts: Track horizontal and vertical pieces separately
- Sort Descending: Process cuts from most expensive to least
- Two Pointers: Compare top of both sorted arrays
- Real Application: Manufacturing, material cutting optimization
- Similar Problems: Rod cutting, matrix chain multiplication (but those need DP)