title

problem link

给你一个二维整数数组 tiles ，其中 tiles[i] = [li, ri] ，表示所有在 li <= j <= ri 之间的每个瓷砖位置 j 都被涂成了白色。

同时给你一个整数 carpetLen ，表示可以放在 任何位置 的一块毯子。

请你返回使用这块毯子，最多 可以盖住多少块瓷砖。

示例 1：

输入：tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
输出：9
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖，所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出，瓷砖无法覆盖超过 9 块瓷砖。

示例 2：

输入：tiles = [[10,11],[1,1]], carpetLen = 2
输出：2
解释：将毯子从瓷砖 10 开始放置。
总共覆盖 2 块瓷砖，所以我们返回 2 。

提示：

• 1 <= tiles.length <= 5 * 104
• tiles[i].length == 2
• 1 <= li <= ri <= 109
• 1 <= carpetLen <= 109
• tiles 互相 不会重叠 。

solution

let me sort out the question.

We are given two key parameters.

first, the tiles, which is a two-dimensional array, and every element of this array is a range, we can call it interval consisting of l and r.

second, the carpetlen, the length of the carpet.

here is my initial idea of solution.

what we need to do is to find the most tiles that can be covered by this carpet. note that the covered tiles must be continueous.

it’s always better to place a carpet at the beginning of a range. the reason is that if you shift a carpet one right, you might cover another white tile, but you definately uncover the previous while tile.

does that sounds great?

So, we sort tiles ranges, and check how many white tiles we can cover, staring from the beginning of each range. To avoid TLE(time limit exceed), we can use the sliding window technique, like the approach of two pointers.

• we track the placement of carpet in i, so the left side is tiles of i of 0.
• when we can cover tiles[j], we add tiles of j to the cover scope, and extend the sliding window by j+=1,
• otherwise, we compute partial cover of tiles of i, total cover is cover + partial.
  • we remove the tiles of i from cover.
  • we move the carpet to the next tile, shrinking the sliding window

so the left pointer will move o(n) times, and right pointer will move o(n) times. total is o(nlogn).

no extra space complexity.

it’s easier and better to calculate the cover + partial, rather than cover minus uncovered.

class Solution:
    def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
        arr = tiles
        arr.sort()
        n = len(arr)
        r = -1
        cur_valid = 0
        ans = 0
        for l in range(n):
            s, e = arr[l]
            while r == -1 or (r < n and arr[r][1] - s + 1 < carpetLen):
                r += 1
                if r < n:
                    cur_valid += arr[r][1] - arr[r][0] + 1
            # 完全覆盖第j个瓷砖
            if r == n:
                ans = max(ans, cur_valid)
            # 第j个瓷砖不能完全覆盖
            else:
                e1 = arr[r][1]
                # 要减去的多余的值
                t = max(0, e1 - max((s + carpetLen), arr[r][0]) + 1)
                ans = max(ans, cur_valid - t)
            cur_valid -= e - s + 1
        return ans