Số lượng hình chữ nhật tối thiểu sau khi lồng nhau trong C++

Cho N hình chữ nhật (w, h). Hình chữ nhật A lồng vào B được nếu wA < wB và hA < hB. Tìm số lượng hình chữ nhật tối thiểu sau khi lồng tối đa.

Ví dụ

Input: {{30,45}, {15,15}, {45,30}, {60,75}}

Output: 2 (lồng {15,15} vào {30,45}, rồi vào {60,75}; {45,30} và {60,75} còn lại)

Thuật toán: Sắp xếp + Binary Search (tìm LIS biến thể)

• Sắp xếp theo width tăng, height giảm (để tránh lồng cùng width).
• Duyệt từ lớn đến nhỏ, duy trì mảng nested lưu height nhỏ nhất của chuỗi lồng độ dài i.
• Dùng binary search tìm vị trí chèn height hiện tại vào nested.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

bool cmp(const pair<int,int>& a, const pair<int,int>& b) {
    if (a.first == b.first) return a.second > b.second;
    return a.first < b.first;
}

int minRectangles(vector<pair<int,int>>& boxes) {
    int n = boxes.size();
    sort(boxes.begin(), boxes.end(), cmp);
    
    vector<pair<int,int>> nested;
    nested.push_back(boxes[n-1]);
    
    for (int i = n-2; i >= 0; --i) {
        int l = 0, r = nested.size()-1;
        while (l <= r) {
            int mid = (l+r)/2;
            if (nested[mid].first == boxes[i].first || nested[mid].second <= boxes[i].second)
                l = mid + 1;
            else
                r = mid - 1;
        }
        if (l == nested.size()) nested.push_back(boxes[i]);
        else {
            nested[l].first = boxes[i].first;
            nested[l].second = boxes[i].second;
        }
    }
    return nested.size();
}

int main() {
    vector<pair<int,int>> boxes = {{30,45}, {15,15}, {45,30}, {60,75}};
    cout << minRectangles(boxes); // 2
    return 0;
}

Kết quả

2

Độ phức tạp: O(N log N) do sắp xếp và binary search.