文章目录
  1. 1.
  2. 2. 后记

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

  • Example 1:
1
2
3
4
5
6
7
8
9
rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]
Return true. All 5 rectangles together form an exact cover of a rectangular region.

  • Example 2:
1
2
3
4
5
6
7
8
rectangles = [
[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
]
Return false. Because there is a gap between the two rectangular regions.

  • Example 3:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
]
Return false. Because there is a gap in the top center.
```
![](https://leetcode.com/static/images/problemset/rectangle_hole.gif)
* Example 4:
```ruby
rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[2,2,4,4]
]
Return false. Because two of the rectangles overlap with each other.


以前LeetCode Contest中的一道题,判断一堆小矩形是否可以组成一个大矩形.
第一步感觉没有什么疑问,先判断小矩形加起来的面积和左下角与右上角组成的大矩形的面积是否一致.
这个面积不一致,那就可以直接返回false了.
然后需要判断小矩形之间没有重叠,这里如果就简单的遍历每两个矩形的话,时间复杂度是O(n^2),那妥妥的超时了.
当时做了不少优化的操作,比如合并小矩形什么的,不过归根结底还是个O(n^2)的算法,一直没有通过.

现在回头再做的话,换了一种思路,直接先按左下角的x坐标和y坐标排序.
然后以X轴坐标为组开始遍历,如果从0至H(大矩形高度)有重叠或者接不上的情况,那么返回false.
遍历完一列之后,就可以往右推进X(最短的矩形宽度).然后再接着遍历下一列.
排序是O(nlogn),后面的遍历,逻辑比较复杂,做一些优化省去一些不必要的遍历的话,一眼看起来是个O(n)的操作.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
# @param {Integer[][]} rectangles
# @return {Boolean}
def is_rectangle_cover(rectangles)
# 将坐标修改成以(0,0)为基准,方便后面计算
nx = nil
ny = nil
rectangles.each{|r|
nx = r[0] if nx == nil || r[0] < nx
ny = r[1] if ny == nil || r[1] < ny
}
if nx != 0 || ny != 0
nx = -nx
ny = -ny
rectangles.each{|r|
r[0] += nx
r[1] += ny
r[2] += nx
r[3] += ny
}
end
max_y = nil
rectangles.each{|r|
max_y = r[3] if max_y == nil || r[3] > max_y
}
# 按x-y排序
rectangles.sort!{|a,b|
if a[0] < b[0]
-1
elsif a[0] > b[0]
1
else
a[1] <=> b[1]
end
}
# 当前竖列
cache = []
# 当前高度
current_y = 0
# 当前x偏移值
x_offset = 0
# 应有高度
height = max_y
# 最小x值
min_x_offset = nil
# 第二小x值
second_min_x_offset = nil
# cache中高度>=current_y的最小idx
cache_idx = 0
rectangles.each{|r|
# x需要往右移动
if r[0] != x_offset
# 移动前把之前列的cache填充
# next row
cache_idx.upto(cache.size-1){|idx|
p = cache[idx]
break if p[0] != current_y
current_y = p[1]
cache_idx += 1
}
# 上一列高度不够 fail
return false if current_y != height
# x没有前进 fail
return false if min_x_offset == x_offset
# 更新x_offset
x_offset = min_x_offset
# 移动x后 当前x值对应不上
return false if r[0] != x_offset
# 重新开始计算新的一列
current_y = 0
# 前面已填充的可以delete掉
ci = 0
while ci < cache.size
p = cache[ci]
if p[2] <= x_offset
cache.delete_at(ci)
ci -= 1
end
# 如果和上一个比较,x值一样且start_y与上一个的end_y一致,则把他们2个合并
if ci > 0 && p[2] == cache[ci-1][2] && p[0] == cache[ci-1][1]
cache[ci][0] = cache[ci-1][0]
cache.delete_at(ci-1)
ci -= 1
end
ci += 1
end
cache_idx = 0
# 选出新的min_x_offset
if second_min_x_offset != nil
# 有第二小的min_x_offset,用第二小的
min_x_offset = second_min_x_offset
else
# 没有第二小的,重新遍历一遍来计算
# 这里比较耗时,所以需要维持一个第二小的x_offset,如果每次都遍历计算,会超时
min_x_offset = nil
cache.each{|r|
min_x_offset = r[2] if min_x_offset == nil || min_x_offset > r[2]
}
end
second_min_x_offset = nil
end
# 先填充cache里的
cache_idx.upto(cache.size-1){|idx|
p = cache[idx]
break if p[0] != current_y
current_y = p[1]
cache_idx += 1
}
# y值接不上 fail
return false if r[1] != current_y
# 放入cache
cache.insert cache_idx,[r[1],r[3],r[2]]
# 更新当前高度
current_y = r[3]
# 计算min_x_offset
if min_x_offset == nil || min_x_offset > r[2]
second_min_x_offset = min_x_offset
min_x_offset = r[2]
end
# 与cache中下一个块重叠了
if cache_idx + 1 < cache.size
# r[3]是当前块的最大Y值,如果比cache中下一块的最小Y值大,说明有重叠,fail
return false if r[3] > cache[cache_idx+1][0]
end
cache_idx += 1
}
return true
end

后记

虽然通过了,不过这堆代码太长太复杂了,照理说应该不用这么麻烦.
于是后来我进讨论区看看大佬们是怎么写的.果然是有简便多的算法的.
第一步确实是先判断面积.第二步判断重叠时,只需遍历一次所有的小矩形.
考虑他们的顶点,如果没有重叠的话,那么除了四个角上的顶点,其他位置的顶点都应该有偶数个.
这个算法就简单多了,O(n)的时间,O(n)的空间.
不过上面O(nlogn)的算法只需300ms,而这个明显是O(n)的算法居然要400ms.也是不知道为什么这么迷.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# @param {Integer[][]} rectangles
# @return {Boolean}
def is_rectangle_cover(rectangles)
return false if rectangles.size == 0
map = {}
min_x = nil
min_y = nil
max_x = nil
max_y = nil
total_area = 0
rectangles.each{|r|
min_x = r[0] if min_x == nil || r[0] < min_x
min_y = r[1] if min_y == nil || r[1] < min_y
max_x = r[2] if max_x == nil || r[2] > max_x
max_y = r[3] if max_y == nil || r[3] > max_y
total_area += ((r[2] - r[0]) * (r[3] - r[1]))
[[r[0],r[1]],[r[0],r[3]],[r[2],r[1]],[r[2],r[3]]].each{|x|
k = "#{x[0]},#{x[1]}"
if map[k]
map.delete(k)
else
map[k] = true
end
}
}
rect_area = ((max_x - min_x) * (max_y - min_y))
[[min_x,min_y],[min_x,max_y],[max_x,min_y],[max_x,max_y]].each{|x|
k = "#{x[0]},#{x[1]}"
return false unless map[k]
}
return map.keys.size == 4 && total_area == rect_area
end
文章目录
  1. 1.
  2. 2. 后记