3219. Minimum Cost for Cutting Cake II | 1789

 1class Solution:
 2    def minimumCost(
 3        self, m: int, n: int, horizontalCut: List[int], verticalCut: List[int]
 4    ) -> int:
 5
 6        # wrong (almost correct) idea:
 7        # c = 0, h = [1,3,5], v = [6,1,1]
 8        # find max(max(h),max(v))
 9        # c = 6, h = [2,6,10], v = [1,1]
10        # c = 16, h = [2,6], v = [2,2]
11        # c = 22, h = [2], v = [3,3]
12        # c = 25, h = [3], v = [3]
13        # c = 28, h = [], v = [4]
14        # c = 32
15
16        # correct idea:
17        # c = 0, h = [1,3,5] (1x), v = [6,1,1] (1x)
18        # find max(max(h),max(v))
19        # c = 6, h = [1,3,5] (2x), v = [1,1] (1x)
20        # c = 16, h = [1,3] (2x), v = [1,1] (2x)
21        # c = 22, h = [1] (2x), v = [1,1] (3x)
22        # c = 24, h = [] (2x), v = [1,1] (4x)
23        # c = 28, h = [] (3x), v = [1] (4x)
24        # c = 32, h = [] (4x), v = [] (4x)
25
26        # impl:
27        # can use two maxheap with h_mult and v_mult, each += 1 when cutting the other dim
28        # tbh we can also just sort - what's the fun tho; I love heapq
29        c, h, v = 0, [], []
30        heapq.heapify(h)
31        heapq.heapify(v)
32        h_mult, v_mult = 1, 1
33
34        for cut in horizontalCut:
35            heapq.heappush(h, -cut)
36        for cut in verticalCut:
37            heapq.heappush(v, -cut)
38
39        while h or v:
40            if h and v:
41                hmax = -h[0]
42                vmax = -v[0]
43                if hmax > vmax:
44                    heapq.heappop(h)
45                    c += hmax * h_mult
46                    v_mult += 1
47                else:
48                    heapq.heappop(v)
49                    c += vmax * v_mult
50                    h_mult += 1
51            elif h:
52                c += -heapq.heappop(h) * h_mult
53            else:
54                c += -heapq.heappop(v) * v_mult
55
56        return c