1465.md

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

Solution 1 (time O(mlogm+nlogn), space O(m+n))

class Solution(object):
    def maxArea(self, h, w, horizontalCuts, verticalCuts):
        """
        :type h: int
        :type w: int
        :type horizontalCuts: List[int]
        :type verticalCuts: List[int]
        :rtype: int
        """
        def cal_max(arr, border):
            ans, pre = 0, 0
            for t in arr:
                ans = max(t - pre, ans)
                pre = t
            return max(ans, border - pre)
        horizontalCuts.sort()
        verticalCuts.sort()
        return (cal_max(horizontalCuts, h) * cal_max(verticalCuts, w) % (10 ** 9 + 7))