SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

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.

Approach

1. Sort and Process Cuts: Start by sorting both hCut and vCut arrays in descending order to prioritize higher cost cuts first.

2. 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.

3. Calculate Total Cost: Accumulate the cost for each cut made based on the current position indices and the cost arrays.

4. 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.

Complexity

• 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) ).

Code

C++

class Solution {
public:
    int 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>());

        int i1 = 0, i2 = 0;
        int 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;
    }
};

Python

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

Java

class Solution {
    public int minimumCost(int m, int n, int[] hCut, int[] vCut) {
        Arrays.sort(hCut);
        Arrays.sort(vCut);

        int i1 = 0, i2 = 0;
        int 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 += hCut[i1++] * (i2 + 1);
        while (i2 < n - 1) res += vCut[i2++] * (i1 + 1);

        return res;
    }
}

JavaScript

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;
};