是我太菜还是被三哥坑了？

最近半年一直都在刷题。lc周赛积分大概在2000左右，虽然不高但是想着面试应该够了。两三周前在密集面试几家公司，绝大部分都挺好，其中有一家大厂的phone，三哥给了我这么道题，写的我怀疑自己是不是还是太菜了：


```
有一条和X轴平行的路。给你一个width表示这条路的宽度。另外给出若干个矩形，每个矩形用2对x-y坐标表示出左上角和右下角的点。矩形是障碍，会堵住这条路。要求返回一个boolean值，判断道路是否通畅。
譬如说路宽100，给的矩形是 [0, -5, 10,100]这条路就被堵上了。如果是 [0, 1, 10,100]就没堵上。
```


这道题确实没有什么复杂算法，用来phone也不过分。但是写着写着我就觉得不太对了：

• 从最左边Dijkstra一层一层扩散到最后边肯定不行。道路宽度是width，万一width很大非常浪费资源。面试官可以说空间复杂不是最优，算法资源浪费太重，挂掉。
• 从X最小的那一列一点点往右判定也不行。万一矩形稀疏，或者分散在0 - 1e9这种很长的空间内，面试官还是以不是最优解可以挂掉你
• 从最左矩形开始一个一个矩形evaluate看有没有block。同时用一个List<int[]>来追踪当前x的道路通常坐标。

这个是我感觉最有希望的。也可能是我速度还是不行，写起来时间根本就不够。我花了大概30分钟连说带写，写了这一套流程：

• 首先让矩形的竖边进行排序，按照x坐标从左到右排好。同时区分清楚是矩形的左竖边还是右竖边。
• 对那些竖边一个个进行遍历。对上一个List<int[]>组合成下一个List<int[]>。譬如说原本是[0,100]都是通的，遇到一个竖边从10到20的矩形，就会变成[0,10],[20,100]。
• 如果任何时候List<int[]>空了就返回否。

后面那部分就相当于一道加强版的蠡口武刘了。另外test case也必须自己写。绝大部分自己想到的test case都过了。面试官画了草图让我自己算出他画的8个矩形的坐标，一共是16个点。最后5分钟发现有一个边界情况没考虑到，两三行代码修一下估计时间也来不及，就说了下想法，面试官说ok。然后两天后拒信发到邮箱。


这两天反省了一下，越想越不明白是不是自己太菜的。因为这道题算法并不难，edge case也不难想，被挂确实不冤。但是怎么感觉写起来这么难受。而且我想到的3个解法中，前两个写出来也有借口挂掉你，最后一个写起来很难在有限时间内写一个完整的code。


所以到底是我太菜还是三哥面试官故意挑的这道看着简单写着麻烦的题恶心人的？如果是后者，我整理一下这道题以后面三哥用了。

牛角尖钻成这样，挺可悲的

ljqchlsw 发表于 2025-01-10 16:26:46
最近面过类似的题，不过矩形换成了圆，当时就用dfs做的，重点就是判断两个图形是否相交吧..

你这个也是典型的并查集的题

miyan 发表于 2025-1-10 18:56
印象里某回LeetCode周赛有这题

如果你是说周赛肆零捌Q4的话。那可是全力扣最难的题，就算放在CF也是难题了...

你太菜 多刷点题

你是不是想多了？ 按照你的描述这题显然给的是左下角和右上角， 只需要左下角和左上角的坐标就行，然后判断是否把0到100全部cover了。也就是你的做法2就是正确思路。

这咋还整出djaaka和排序了？ 我估计三哥躲在屏幕背后笑这人怎么脑补出这么复杂的。。

-baidu 1point3acres

匿名用户 发表于 2025-1-10 14:48
你是不是想多了？ 按照你的描述这题显然给的是左下角和右上角， 只需要左下角和左上角的坐标就行，然后判断 ...

是好多个矩形叠在一起，不是一个。最后的test case是8个矩形一起堵路。
我感觉思路2和思路3差不多。思路2是x一个一个遍历，在矩阵稀疏的情况下并不最优。而且问题在于如果test case类似于如图，光看两个角的坐标并不够。

hrj581 发表于 2025-01-10 14:52:24
是好多个矩形叠在一起，不是一个。最后的test case是8个矩形一起堵路。
我感觉思路2和思路3差不多。思路2是x一个一个遍历，在矩阵稀疏的情况下并不最优。

害，那你说清楚嘛！ 你这个题width的区间是多少，如果最大width是100的话也没问题。维持一个记录当前区间的array然后一个一个检查看看是全被覆盖了还是有缝隙。

匿名用户 发表于 2025-1-10 15:07
害，那你说清楚嘛！ 你这个题width的区间是多少，如果最大width是100的话也没问题。

宽度也是个变量，所以我想着如果是解法1或者解法2的话也会被面试官以复杂度不最优挂掉

hrj581 发表于 2025-01-10 15:09:26
宽度也是个变量，所以我想着如果是解法1或者解法2的话也会被面试官以复杂度不最优挂掉

你做的没有错，这个题只能这样暴力求解，维持一个当前还在的矩形list，然后每个检查点一个一个检查，有缝隙就过没缝隙就retuen false。

ps： 你这画图网站是啥，滑得还挺好看。

我随便想一下，感觉就是x轴扫描线扫一下看看x轴方向有没有漏洞，然后y轴在扫一遍看看有没有漏洞就可以了。扫的时候注意上下界。不是很复杂。
或者x轴做投影，然后y轴做投影，然后分别merge interval，看看是不是全覆盖。

匿名用户 发表于 2025-1-10 15:16
你做的没有错，这个题只能这样暴力求解，维持一个当前还在的矩形list，然后每个检查点一个一个检查，有缝 ...

我想了想也是这么解挑不出毛病了，奈何写起来真的很累，写到最后时间不够。
那个图就是随手开了个画图画的..