1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/

Python

Greedy

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        horizontalCuts.sort()
        verticalCuts.sort()

        max_h = max(horizontalCuts[0], h-horizontalCuts[-1])
        max_w = max(verticalCuts[0], w-verticalCuts[-1])

        for i in range(1, len(horizontalCuts)):
            interval_h = horizontalCuts[i] - horizontalCuts[i-1]
            max_h = max(max_h, interval_h)

        for j in range(1, len(verticalCuts)):
            interval_w = verticalCuts[j] - verticalCuts[j-1]
            max_w = max(max_w, interval_w)

        return (max_h * max_w) % (10**9 + 7)