推 JIWP: 大師我好崇拜你 03/25 23:43
推 oin1104: 大師 03/25 23:47
https://leetcode.com/problems/check-if-grid-can-be-cut-into-sections
3394. Check if Grid can be Cut into Sections
給你一個數字n表示n*n的二維空間，rectangles[i] = [startx, starty, endx, endy]
表示多個矩形的左下角座標和右上角座標，求出我們是否可以將這個空間切成三塊(橫或
縱切)，使每個矩形不橫跨其他區域且每個區域至少有一個矩形。
https://assets.leetcode.com/uploads/2024/10/23/tt1drawio.png
思路:
跟昨天那題類似，我們把每個矩形的橫座標和縱座標看成一個區間，然後把交集的區域
兩兩合併，可以得到橫切或縱切的不交合區間，如果最後剩下的區間大於等於3個只要
隨變挑兩個縫縫切下去就變成合法的三塊了，比較需要注意的是 [1,2] 和 [2,3] 不算
是交合所以要用 <= 判斷。
Java Code:
---------------------------------------------------
class Solution {
public boolean checkValidCuts(int n, int[][] rectangles) {
List<int[]> xInterval = new ArrayList<>();
List<int[]> yInterval = new ArrayList<>();
for (int[] rectangle : rectangles) {
xInterval.add(new int[]{rectangle[0], rectangle[2]});
yInterval.add(new int[]{rectangle[1], rectangle[3]});
}
xInterval.sort(Comparator.comparingInt(x -> x[0]));
yInterval.sort(Comparator.comparingInt(x -> x[0]));
List<int[]> mergedInterval = new ArrayList<>();
mergedInterval.add(xInterval.get(0));
for (int[] interval : xInterval) {
int[] last = mergedInterval.get(mergedInterval.size() - 1);
if (last[1] <= interval[0]) {
mergedInterval.add(new int[]{interval[0], interval[1]});
} else {
last[1] = Math.max(last[1], interval[1]);
}
}
if (mergedInterval.size() >= 3) {
return true;
}
mergedInterval = new ArrayList<>();
mergedInterval.add(yInterval.get(0));
for (int[] interval : yInterval) {
int[] last = mergedInterval.get(mergedInterval.size() - 1);
if (last[1] <= interval[0]) {
mergedInterval.add(new int[]{interval[0], interval[1]});
} else {
last[1] = Math.max(last[1], interval[1]);
}
}
return mergedInterval.size() >= 3;
}
}
---------------------------------------------------
--
https://i.imgur.com/ZfdGodg.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1742917342.A.3C8.html