Create perfect-rectangle.cpp

kamyu104 · web-flow · commit 46b30ebbca6e · 2016-08-29T22:34:30.000+08:00
diff --git a/C++/perfect-rectangle.cpp b/C++/perfect-rectangle.cpp
@@ -0,0 +1,49 @@
+// Time:  O(n)
+// Space: O(n)
+
+class Solution {
+public:
+    bool isRectangleCover(vector<vector<int>>& rectangles) {
+        enum DIR {L = 0, B = 1, R = 2, T = 3};
+        int left = numeric_limits<int>::max(), bottom = numeric_limits<int>::max(),
+            right = numeric_limits<int>::min(), top = numeric_limits<int>::min();
+        for (const auto& rect : rectangles) {
+            left = min(left, rect[L]);
+            bottom = min(bottom, rect[B]);
+            right = max(right, rect[R]);
+            top = max(top, rect[T]);
+        }
+
+        using P = pair<pair<int, int>, int>;
+        enum CORNER {LB = 1, RB = 2, LT = 4, RT = 8};
+        unordered_map<int, unordered_map<int, int>> corner_count;
+        vector<P> corners{{{L, B}, LB}, {{R, B}, RB}, {{L, T}, LT}, {{R, T}, RT}};
+        for (const auto& rect : rectangles) {
+            for (const auto& corner : corners) {
+                const auto x = rect[corner.first.first];
+                const auto y = rect[corner.first.second];
+                if (corner_count[x][y] & corner.second) {
+                    return false;
+                }
+                corner_count[x][y] |= corner.second;
+            }
+        }
+
+        bool is_valid[16] = {false};
+        is_valid[LB | RB] = is_valid[LB | LT] = is_valid[RB | RT] = is_valid[LT | RT] = is_valid[LB | RB | LT | RT] = true;
+        for (auto itx = corner_count.begin(); itx != corner_count.end(); ++itx) {
+            const auto x = itx->first;
+            for (auto ity = itx->second.begin(); ity != itx->second.end(); ++ity) {
+                int y = ity->first;
+                int mask = ity->second;
+                if ((left < x && x < right) || (bottom < y && y < top)) {
+                    if (!is_valid[mask]) {
+                        return false;
+                    }
+                }
+            }
+        }
+
+        return true;
+    }
+};
