391. Perfect Rectangle

📋 Đề Bài

Given an array rectangles where rectangles[i] = [x_i, y_i, a_i, b_i] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (x_i, y_i) and the top-right point of it is (a_i, b_i).

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

Example 1:

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.

Example 2:

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.

Example 3:

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.

Constraints:

1 <= rectangles.length <= 2 * 10⁴
rectangles[i].length == 4
-10⁵ <= x_i, y_i, a_i, b_i <= 10⁵

🧠 Thuật Toán & Kỹ Thuật

Bit Manipulation (Thao tác bit)

⏱️ Thời gian O(n²)

💾 Không gian O(n)

💻 Lời Giải

C++ 0391-perfect-rectangle.cpp

#define INSERT 1
#define DELETE 0

using ll = long long;

class Solution {
public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        vector<vector<ll>> events;
        ll sum = 0;
        ll xMax = INT_MIN, yMax = INT_MIN;
        ll xMin = INT_MAX, yMin = INT_MAX;
        
        for (vector<int> &rectangle : rectangles) {
            ll x1 = rectangle[0];
            ll y1 = rectangle[1];
            ll x2 = rectangle[2];
            ll y2 = rectangle[3];
            
            sum += 1LL*(y2 - y1)*(x2 - x1);
            
            xMin = min(xMin, x1);
            xMax = max(xMax, x2);
            yMin = min(yMin, y1);
            yMax = max(yMax, y2);
            
            events.push_back({x1, INSERT, y1, y2});
            events.push_back({x2, DELETE, y1, y2});
        }

        sort(events.begin(), events.end());
        
        multiset<pair<ll, ll>> line;
        
        for (vector<ll> &event : events) {
            ll curr = event[0];
            ll choose = event[1];
            ll y1 = event[2], y2 = event[3];
            
            if (choose == INSERT) {
                auto it = line.lower_bound({y1, y2});
                
                if (it != line.end() and it->first < y2) {
                    return false;
                }
                
                if (it != line.begin() and (--it)->second > y1) {
                    return false;
                }
                
                line.insert({y1, y2});
            }
            else {
                line.erase(line.lower_bound({y1, y2}));
            }
        }
        
        return sum == 1LL*(yMax - yMin)*(xMax - xMin);
    }
};