Dare2Solve
To minimize the total cost, consider making cuts starting from the most expensive ones, ensuring that each new piece is minimized in cost before making further cuts. This approach ensures that the most expensive cuts are made first, thereby potentially reducing the overall cost.
Sort and Process Cuts: Start by sorting both hCut
and vCut
arrays in descending order to prioritize higher cost cuts first.
Simulate Cutting Process: Initialize variables to track current positions (i1
for horizontal and i2
for vertical) and the accumulated cost (totalCost
). Iterate through both arrays, making cuts and updating positions until all cuts are made.
Calculate Total Cost: Accumulate the cost for each cut made based on the current position indices and the cost arrays.
Return Result: Once all cuts are simulated, return the totalCost
which represents the minimum total cost to cut the entire cake into 1 x 1 pieces.
Time Complexity: Sorting the arrays takes ( O((m-1) log (m-1) + (n-1) log (n-1)) ) time. Simulating the cuts takes ( O(m + n) ) time. Thus, the overall time complexity is ( O((m+n) log (m+n)) ).
Space Complexity: Sorting requires ( O(m + n) ) additional space for arrays. Other variables used are constant space. Hence, the space complexity is ( O(m + n) ).
class Solution {
public:
long long minimumCost(int m, int n, vector<int>& hCut, vector<int>& vCut) {
sort(hCut.begin(), hCut.end(), greater<int>());
sort(vCut.begin(), vCut.end(), greater<int>());
long long i1 = 0, i2 = 0;
long long res = 0;
while (i1 < m - 1 && i2 < n - 1) {
if (hCut[i1] > vCut[i2]) res += hCut[i1++] * (i2 + 1);
else res += vCut[i2++] * (i1 + 1);
}
while (i1 < m - 1) res += hCut[i1++] * (i2 + 1);
while (i2 < n - 1) res += vCut[i2++] * (i1 + 1);
return res;
}
};
class Solution:
def minimumCost(self, m: int, n: int, hCut: List[int], vCut: List[int]) -> int:
hCut.sort()
vCut.sort()
i1, i2 = 0, 0
res = 0
while i1 < m - 1 and i2 < n - 1:
if hCut[i1] > vCut[i2]:
res += hCut[i1] * (i2 + 1)
i1 += 1
else:
res += vCut[i2] * (i1 + 1)
i2 += 1
while i1 < m - 1:
res += hCut[i1] * (i2 + 1)
i1 += 1
while i2 < n - 1:
res += vCut[i2] * (i1 + 1)
i2 += 1
return res
class Solution {
public long minimumCost(int m, int n, int[] hCut, int[] vCut) {
Arrays.sort(hCut);
Arrays.sort(vCut);
int i1 = 0, i2 = 0;
long res = 0;
while (i1 < m - 1 && i2 < n - 1) {
if (hCut[i1] > vCut[i2]) res += (long) hCut[i1++] * (i2 + 1);
else res += (long) vCut[i2++] * (i1 + 1);
}
while (i1 < m - 1) res += (long) hCut[i1++] * (i2 + 1);
while (i2 < n - 1) res += (long) vCut[i2++] * (i1 + 1);
return res;
}
}
var minimumCost = function (m, n, hCut, vCut) {
hCut.sort((a, b) => b - a);
vCut.sort((a, b) => b - a);
var i1 = 0;
var i2 = 0;
var res = 0;
while (i1 < m - 1 && i2 < n - 1) {
if (hCut[i1] > vCut[i2]) res += hCut[i1++] * (i2 + 1);
else res += vCut[i2++] * (i1 + 1);
}
while (i1 < m - 1) res += hCut[i1++] * (i2 + 1);
while (i2 < n - 1) res += vCut[i2++] * (i1 + 1);
return res;
};