ซองจดหมายรูสเซียใน C++ (Russian Doll Envelopes)

ภาพรวมปัญหา

ให้ซองจดหมายหลายใบ แต่ละใบมี (width, height) ใส่ซองได้ก็ต่อเมื่อ width และ height ทั้งคู่น้อยกว่าอีกใบ หาจำนวนซองสูงสุดที่ซ้อนกันได้ (Longest Increasing Subsequence 2 มิติ)

ตัวอย่าง

[[5,5], [6,4], [6,8], [2,3]] → Output: 3
ลำดับ: [2,3] → [5,5] → [6,8]

วิธีแก้ปัญหา: LIS แบบ Binary Search

1. เรียงซอง: width ขึ้น, ถ้า width เท่ากัน height ลง (สำคัญ! ป้องกันนับซ้ำ width เดียวกัน)
2. หา LIS ของ height ด้วย Binary Search (Patience Sorting)
3. เก็บ array ret ที่ ret[i] = ค่า height สุดท้ายที่น้อยที่สุดของ LIS ความยาว i+1
4. สำหรับแต่ละซอง: binary search หาตำแหน่งแรกใน ret ที่ ≥ height ปัจจุบัน แล้วแทนที่ (หรือ push_back ถ้าใหญ่กว่าทุกตัว)
5. คำตอบ = ret.size()

โค้ด 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.size() == 0) return 0;
        vector<int> ret;
        for (int i = 0; i < v.size(); i++) {
            int x = v[i][1];
            int low = 0, high = (int)ret.size() - 1, curr = 0;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (ret[mid] < x) {
                    curr = mid + 1;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            if (curr < 0) continue;
            if (curr >= (int)ret.size()) ret.push_back(x);
            else ret[curr] = x;
        }
        return ret.size();
    }
};

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

การวิเคราะห์ความซับซ้อน

• เวลา: O(n log n) — เรียง + binary search ทุกตัว
• พื้นที่: O(n) — array ret