Minimum Cost to cut a board into squares

A board of length m and width n is given, we need to break this board into m*n squares such that cost of breaking is minimum. cutting cost for each edge will be given for the board. In short we need to choose such a sequence of cutting such that cost is minimized. Examples:

For above board optimal way to cut into square is:
Total minimum cost in above case is 42. It is 
evaluated using following steps.

Initial Value : Total_cost = 0
Total_cost = Total_cost + edge_cost * total_pieces

Cost 4 Horizontal cut         Cost = 0 + 4*1 = 4
Cost 4 Vertical cut        Cost = 4 + 4*2 = 12
Cost 3 Vertical cut        Cost = 12 + 3*2 = 18
Cost 2 Horizontal cut        Cost = 18 + 2*3 = 24
Cost 2 Vertical cut        Cost = 24 + 2*3 = 30
Cost 1 Horizontal cut        Cost = 30 + 1*4 = 34
Cost 1 Vertical cut        Cost = 34 + 1*4 = 38
Cost 1 Vertical cut        Cost = 38 + 1*4 = 42
// we perform cuts on highest cost edge as early as possible
class Solution {
    public int minimumCostOfBreaking(Integer X[], Integer Y[], int m, int n) {
        int res = 0;
        // sort the horizontal cost in reverse order
        Arrays.sort(X, Collections.reverseOrder());
        // sort the vertical cost in reverse order
        Arrays.sort(Y, Collections.reverseOrder());
        // initialize current width as 1
        int horizontalPieces = 1, verticalPieces = 1;
        // loop untill one or both
        // cost array are processed
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (X[i] > Y[j]) {
                res += X[i] * verticalPieces;
                horizontalPieces++;
                i++;
            } else {
                res += Y[j] * horizontalPieces;
                verticalPieces++;
                j++;
            }
        }
        int total = 0;
        while (i < m)
            total += X[i++];
        res += total * verticalPieces;
        total = 0;
        while (j < n)
            total += Y[j++];
        res += total * horizontalPieces;
        return res;
    }
}

Last updated