perfect-rectangle

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Given an array <code>rectangles</code> where <code>rectangles[i] = [xi, yi, ai, bi]</code> represents an axis-aligned rectangle. The bottom-left point of the rectangle is <code>(xi, yi)</code> and the top-right point of it is <code>(ai, bi)</code>.

Return <code>true</code> if all the rectangles together form an exact cover of a rectangular region.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perectrec1-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output: true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfectrec2-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output: false
Explanation: Because there is a gap between the two rectangular regions.
</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfecrrec4-plane.jpg" style="width: 300px; height: 294px;" />
<pre>
Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output: false
Explanation: Because two of the rectangles overlap with each other.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= rectangles.length &lt;= 2 * 104</code></li>
	<li><code>rectangles[i].length == 4</code></li>
	<li><code>-105 &lt;= xi &lt; ai &lt;= 105</code></li>
	<li><code>-105 &lt;= yi &lt; bi &lt;= 105</code></li>
</ul>

isRectangleCover

Perfect Rectangle

Geometry

Array

Hash Table

Math

Sweep Line

&#32473;&#20320;&#19968;&#20010;&#25968;&#32452; <code>rectangles</code> &#65292;&#20854;&#20013; <code>rectangles[i] = [xi, yi, ai, bi]</code> &#34920;&#31034;&#19968;&#20010;&#22352;&#26631;&#36724;&#24179;&#34892;&#30340;&#30697;&#24418;&#12290;&#36825;&#20010;&#30697;&#24418;&#30340;&#24038;&#19979;&#39030;&#28857;&#26159; <code>(xi, yi)</code> &#65292;&#21491;&#19978;&#39030;&#28857;&#26159; <code>(ai, bi)</code> &#12290;

&#22914;&#26524;&#25152;&#26377;&#30697;&#24418;&#19968;&#36215;&#31934;&#30830;&#35206;&#30422;&#20102;&#26576;&#20010;&#30697;&#24418;&#21306;&#22495;&#65292;&#21017;&#36820;&#22238; <code>true</code> &#65307;&#21542;&#21017;&#65292;&#36820;&#22238; <code>false</code> &#12290;
&nbsp;

&#31034;&#20363; 1&#65306;
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perectrec1-plane.jpg" style="height: 294px; width: 300px;" />
<pre>
&#36755;&#20837;&#65306;rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
&#36755;&#20986;&#65306;true
&#35299;&#37322;&#65306;5 &#20010;&#30697;&#24418;&#19968;&#36215;&#21487;&#20197;&#31934;&#30830;&#22320;&#35206;&#30422;&#19968;&#20010;&#30697;&#24418;&#21306;&#22495;&#12290; 
</pre>

&#31034;&#20363; 2&#65306;
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfectrec2-plane.jpg" style="height: 294px; width: 300px;" />
<pre>
&#36755;&#20837;&#65306;rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
&#36755;&#20986;&#65306;false
&#35299;&#37322;&#65306;&#20004;&#20010;&#30697;&#24418;&#20043;&#38388;&#26377;&#38388;&#38548;&#65292;&#26080;&#27861;&#35206;&#30422;&#25104;&#19968;&#20010;&#30697;&#24418;&#12290;</pre>

&#31034;&#20363; 3&#65306;
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/27/perfecrrec4-plane.jpg" style="height: 294px; width: 300px;" />
<pre>
&#36755;&#20837;&#65306;rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
&#36755;&#20986;&#65306;false
&#35299;&#37322;&#65306;&#22240;&#20026;&#20013;&#38388;&#26377;&#30456;&#20132;&#21306;&#22495;&#65292;&#34429;&#28982;&#24418;&#25104;&#20102;&#30697;&#24418;&#65292;&#20294;&#19981;&#26159;&#31934;&#30830;&#35206;&#30422;&#12290;</pre>

&nbsp;

&#25552;&#31034;&#65306;

<ul>
	<li><code>1 &lt;= rectangles.length &lt;= 2 * 104</code></li>
	<li><code>rectangles[i].length == 4</code></li>
	<li><code>-105 &lt;= xi &lt; ai &lt;= 105</code></li>
	<li><code>-105 &lt;= yi &lt; bi &lt;= 105</code></li>
</ul>

Sunbelt Computer Software

PL/B Language Development and Support