做个平台网站怎么做的,个人做论坛网站,做会计应关注什么网站,深圳网站建设在哪里找文章目录1. 题目2. 解题1. 题目
给你一个二维整数数组 tiles #xff0c;其中 tiles[i] [li, ri] #xff0c;表示所有在 li j ri 之间的每个瓷砖位置 j 都被涂成了白色。
同时给你一个整数 carpetLen #xff0c;表示可以放在 任何位置 的一块毯子。
请你返回…
文章目录1. 题目2. 解题1. 题目
给你一个二维整数数组 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 * 10^4
tiles[i].length 2
1 li ri 10^9
1 carpetLen 10^9
tiles 互相 不会重叠 。来源力扣LeetCode 链接https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
先排序区间求区间的前缀砖块个数遍历每个区间 i在 [i, n-1] 中二分查找 最后一个区间 j (titles[j][0] titles[i][0]carpetLen), j 能够被盖住部分或者全部
class Solution:def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) - int:n len(tiles)prevsum [0]*ntiles.sort(keylambda x : x[0])for i in range(n):prevsum[i] (prevsum[i-1] if i0 else 0) tiles[i][1]-tiles[i][0]1ans 0for i in range(n):val tiles[i][0] carpetLen - 1if val tiles[i][1]:return carpetLenl, r, j i, n-1, -1 # 二分查找 左端点 val 的最后一个区间while l r:mid (lr)//2if tiles[mid][0] val:r mid-1else:if midn-1 or tiles[mid1][0] val:j midbreakelse:l mid1cover prevsum[j-1] - (0 if i0 else prevsum[i-1]) min(val, tiles[j][1]) - tiles[j][0] 1ans max(ans, cover)return ans824 ms 31 MB Python3 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
