力扣2201. 统计可以提取的工件

〇〇

2201. 统计可以提取的工件 https://leetcode.cn/problems/cou ... t-can-be-extracted/
中等
相关标签
相关企业
提示
存在一个 n x n 大小、下标从 0 开始的网格，网格中埋着一些工件。给你一个整数 n 和一个下标从 0 开始的二维整数数组 artifacts ，artifacts 描述了矩形工件的位置，其中 artifacts = [r1i, c1i, r2i, c2i] 表示第 i 个工件在子网格中的填埋情况：

(r1i, c1i) 是第 i 个工件 左上 单元格的坐标，且
(r2i, c2i) 是第 i 个工件 右下 单元格的坐标。
你将会挖掘网格中的一些单元格，并清除其中的填埋物。如果单元格中埋着工件的一部分，那么该工件这一部分将会裸露出来。如果一个工件的所有部分都都裸露出来，你就可以提取该工件。

给你一个下标从 0 开始的二维整数数组 dig ，其中 dig = [ri, ci] 表示你将会挖掘单元格 (ri, ci) ，返回你可以提取的工件数目。

生成的测试用例满足：

不存在重叠的两个工件。
每个工件最多只覆盖 4 个单元格。
dig 中的元素互不相同。


示例 1：


输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1]]
输出：1
解释：
不同颜色表示不同的工件。挖掘的单元格用 'D' 在网格中进行标记。
有 1 个工件可以提取，即红色工件。
蓝色工件在单元格 (1,1) 的部分尚未裸露出来，所以无法提取该工件。
因此，返回 1 。
示例 2：


输入：n = 2, artifacts = [[0,0,0,0],[0,1,1,1]], dig = [[0,0],[0,1],[1,1]]
输出：2
解释：红色工件和蓝色工件的所有部分都裸露出来（用 'D' 标记），都可以提取。因此，返回 2 。


提示：

1 <= n <= 1000
1 <= artifacts.length, dig.length <= min(n2, 105)
artifacts.length == 4
dig.length == 2
0 <= r1i, c1i, r2i, c2i, ri, ci <= n - 1
r1i <= r2i
c1i <= c2i
不存在重叠的两个工件
每个工件 最多 只覆盖 4 个单元格
dig 中的元素互不相同
通过次数
9.2K
提交次数
18.4K
通过率
50.2%

〇〇

算出每个工件覆盖的格子，数挖完不剩的工件个数

〇〇

想用not exists写，不成功，写了个count比较的
with artifacts(a) as (select unnest([[0,0,0,0],[0,1,1,1]])),
dig(d) as(select  unnest([[0,0],[0,1],[1,1]]))
select  a from artifacts,dig where d[1] between a[1] and a[2] and  d[2] between a[3] and a[4] group by a having count(d)= (a[3]+1-a[1])*(a[4]+1-a[2]);

┌──────────────┐
│      a       │
│   int32[]    │
├──────────────┤
│ [0, 0, 0, 0] │
│ [0, 1, 1, 1] │
└──────────────┘



with artifacts(a) as (select unnest([[0,0,0,0],[0,1,1,1]])),
dig(d) as(select  unnest([[0,0],[0,1]]))
select  a from artifacts,dig where d[1] between a[1] and a[2] and  d[2] between a[3] and a[4] group by a having count(d)= (a[3]+1-a[1])*(a[4]+1-a[2]);
┌──────────────┐
│      a       │
│   int32[]    │
├──────────────┤
│ [0, 0, 0, 0] │
└──────────────┘

newkid

工件是矩形，挖掘区域也是矩形，只需计算工件矩形被挖掘区域覆盖的个数，这不是超级简单的吗？判断对角两个顶点就行。还是我理解有误？

newkid

哦，原来挖掘区域不是一个矩形，是零散的点，那么也是超级简单，就像你这样INNER JOIN然后看看点数是否等于矩形面积就行了。

〇〇

判断天际线应该也可以用到这种between and，就不用把横坐标都填满了