LeetCode笔记：Biweekly Contest 54 (补发)

class Solution:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        ranges = sorted([x for x in ranges if x[1] >= left and x[0] <= right])
        n = len(ranges)
        if n == 0:
            return False
        _min, _max = ranges[0][0], ranges[0][1]
        for bg, ed in ranges[1:]:
            if bg > _max+1:
                return False
            _max = max(_max, ed)
        return _min <= left and _max >= right

class Solution:
    def chalkReplacer(self, chalk: List[int], k: int) -> int:
        n = len(chalk)
        chalk = [0] + list(accumulate(chalk))
        k = k % chalk[-1]
        idx = bisect.bisect_right(chalk, k)-1
        return idx

class Solution:
    def largestMagicSquare(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        sgrid = [[0 for _ in range(m+1)] for _ in range(n+1)]
        for i in range(n):
            for j in range(m):
                sgrid[i+1][j+1]=grid[i][j] + sgrid[i+1][j] + sgrid[i][j+1] - sgrid[i][j]
        
        k = min(n, m)
        while k > 1:
            for i in range(n-k+1):
                for j in range(m-k+1):
                    s1 = sum(grid[i+l][j+l] for l in range(k))
                    s2 = sum(grid[i+l][j+k-1-l] for l in range(k))
                    if s1 != s2:
                        continue
                    s = s1
                    if all(sgrid[i+l+1][j+k]-sgrid[i+l+1][j]-sgrid[i+l][j+k]+sgrid[i+l][j] == s for l in range(k)) and all(sgrid[i+k][j+l+1]-sgrid[i+k][j+l]-sgrid[i][j+l+1]+sgrid[i][j+l] == s for l in range(k)):
                        return k
            k -= 1
        return k