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 |
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. |
Example 4:
|
1 2 3 4 5 6 7 8 |
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. |
Solution: Counting corner points
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: bool isRectangleCover(vector<vector<int>>& rectangles) { set<pair<int, int>> corners; int area = 0; for (const auto& rect : rectangles) { pair<int, int> p1{rect[0], rect[1]}; pair<int, int> p2{rect[2], rect[1]}; pair<int, int> p3{rect[2], rect[3]}; pair<int, int> p4{rect[0], rect[3]}; for (const auto& p : {p1, p2, p3, p4}) { const auto& ret = corners.insert(p); if (!ret.second) corners.erase(ret.first); } area += (p3.first - p1.first) * (p3.second - p1.second); } if (corners.size() != 4) return false; const auto& p1 = *begin(corners); const auto& p3 = *rbegin(corners); return area == (p3.first - p1.first) * (p3.second - p1.second); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment