Bài toán bọc thư (Russian Doll Envelopes) trong C++

Cho danh sách phong bì [width, height]. Một phong bì có thể bỏ vào phong bì khác nếu cả chiều rộng và chiều cao đều nhỏ hơn. Tìm số lượng phong bì lớn nhất có thể lồng nhau.

Ví dụ

[[5,5], [6,4], [6,8], [2,3]] → Kết quả: 3 ([2,3] → [5,5] → [6,8]).

Thuật toán: LIS (Dãy con tăng dài nhất) 2D

1. Sắp xếp:
   • Chiều rộng tăng dần.
   • Nếu rộng bằng nhau → chiều cao giảm dần (để tránh chọn 2 phong bì cùng rộng).
2. Tìm LIS trên mảng chiều cao sau khi sắp xếp.
3. Dùng thuật toán O(n log n) với mảng ret lưu giá trị cuối nhỏ nhất của dãy con độ dài .

Tại sao sắp xếp chiều cao giảm khi rộng bằng?

Nếu cùng rộng, không thể lồng nhau. Sắp giảm dần đảm bảo khi chạy LIS, chỉ chọn được tối đa 1 phong bì trong nhóm cùng rộng.

Cài đặt C++

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

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b) {
        if (a[0] == b[0]) return a[1] > b[1];
        return a[0] < b[0];
    }

    int maxEnvelopes(vector<vector<int>>& v) {
        sort(v.begin(), v.end(), cmp);
        if (v.empty()) return 0;
        vector<int> ret;
        for (auto& env : v) {
            int h = env[1];
            int low = 0, high = (int)ret.size() - 1, curr = 0;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (ret[mid] < h) {
                    curr = mid + 1;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            if (curr >= (int)ret.size()) ret.push_back(h);
            else ret[curr] = h;
        }
        return ret.size();
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{5,5}, {6,4}, {6,8}, {2,3}};
    cout << ob.maxEnvelopes(v);
    return 0;
}

Độ phức tạp

• Thời gian: O(n log n) — sắp xếp + LIS nhị phân.
• Không gian: O(n).

Input / Output

Input:  {{5,5}, {6,4}, {6,8}, {2,3}}
Output: 3