前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 0391 - Perfect Rectangle

LeetCode 0391 - Perfect Rectangle

作者头像
Reck Zhang
发布2021-08-11 11:06:17
1900
发布2021-08-11 11:06:17
举报
文章被收录于专栏:Reck Zhang

Perfect Rectangle

Desicription

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:

代码语言:javascript
复制
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:

代码语言:javascript
复制
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:

代码语言:javascript
复制
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:

代码语言:javascript
复制
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

代码语言:javascript
复制
class Solution {
public:
    bool isRectangleCover(const std::vector<std::vector<int>>& rectangles) {
        int left = INT_MAX;
        int right = INT_MIN;
        int top = INT_MIN;
        int bottom = INT_MAX;
        auto set = std::set<std::pair<int, int>>{};
        int sumArea = 0;
        for(auto& rectangle : rectangles) {
            left = std::min(left, rectangle[0]);
            right = std::max(right, rectangle[2]);
            top = std::max(top, rectangle[3]);
            bottom = std::min(bottom, rectangle[1]);

            static const auto map = std::vector<std::pair<int, int>> {
                    {0, 1},
                    {2, 3},
                    {2, 1},
                    {0, 3},
            };

            for(const auto& it : map) {
                std::pair<int, int> currentPoint = {rectangle[it.first], rectangle[it.second]};
                if(set.find(currentPoint) != set.end()) {
                    set.erase(currentPoint);
                } else {
                    set.insert(currentPoint);
                }
            }
            sumArea += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);
        }

        return !(set.size() != 4 || set.find({left, top}) == set.end() || set.find({left, bottom}) == set.end() || set.find({right, top}) == set.end() || set.find({right, bottom}) == set.end() || sumArea != ((right - left) * (top - bottom)));
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-09-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Perfect Rectangle
    • Desicription
      • Solution
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档