核心思想就是:能夠正好圍成一個(gè)矩形的情況就是:

有且只有:

- 最左下 最左上 最右下 最右上 的四個(gè)點(diǎn)只出現(xiàn)過一次,其他肯定是成對(duì)出現(xiàn)的(保證完全覆蓋)

- 上面四個(gè)點(diǎn)圍成的面積,正好等于所有子矩形的面積之和(保證不重復(fù))

掃描線算法

false, 和 true就是常規(guī)掃描線算法里面的start, end object的屬性。

對(duì)于false的 也就是left point of a rectangle, 我們采用他的left x.

對(duì)于true的，也就是right point of a rectangle 我們采用他的right x。

Top和Bot 意思就是當(dāng)前見過的所有Rectangle 里的最高的地方，和最低的地方。

Time 他這里的意思是: 寬度， left 或者right。這是一個(gè)很容易錯(cuò)的地方！

很難理解的地方： RectLife里的compareTo.

意思是如果這個(gè)rectangle跟另一個(gè)Rectangle的width x值一樣的話，我們要比較一下他們的left x 的大小。因?yàn)槲覀冎氨容^的width一樣可能只是A的left跟B的right x一樣。我們要把靠近左邊的Rectangle優(yōu)先處理

如果這個(gè)rectangle跟另一個(gè)Rectangle的width x值不一樣的話。

我們有可能組成高度ok的東西，但是中間假設(shè)有一個(gè)gap就完蛋了。所以對(duì)于所有在一個(gè)x點(diǎn)的，我們判斷能不能達(dá)到一樣的高度。pq.peek().time == time...

PriorityQueue的排序順序是按x點(diǎn)time來比的，如果x點(diǎn)一樣，按照rect.l - that.rect.l也就是比x width。

TreeSet<> 用來裝Rect的object，如果以前看過一個(gè)一毛一樣的就不管了

跟掃描線一樣，碰到start 加入set,【可以認(rèn)為是一個(gè)stack】，碰到end remove (rl.rect).

recLife object有一個(gè)rect的object。可以通過他remove from stack.