หาจำนวนสี่เหลี่ยมผืนผ้าที่เหลือขั้นต่ำหลังจากใส่ซ้อนกันใน C++

โจทย์: กำหนด N สี่เหลี่ยมผืนผ้า (width, height) หาจำนวนสี่เหลี่ยมที่เหลือขั้นต่ำหลังจากใส่ซ้อนกัน (nesting) ได้ กฎ: R1 ใส่ใน R2 ได้ก็ต่อเมื่อ W1 < W2 และ H1 < H2

ตัวอย่าง: {{30,45}, {15,15}, {45,30}, {60,75}} → คำตอบ 2 (ใส่ {15,15} ใน {30,45} แล้วใส่ใน {60,75} เหลือ {45,30} และ {60,75})

อัลกอริธึม: Greedy + Binary Search (LIS แบบปรับ)

1. Sort สี่เหลี่ยม: width ขึ้น, height ลง (เวลา width เท่ากัน)
2. Maintain array nested เก็บ "หน้าสุดท้าย" ของแต่ละ chain ที่เป็นไปได้
3. วนจากสี่เหลี่ยมใหญ่สุดไปเล็กสุด:
   • Binary search หา chain แรกที่ใส่ได้ (width และ height มากกว่าสี่เหลี่ยมปัจจุบัน)
   • ถ้าไม่มี → สร้าง chain ใหม่
   • ถ้ามี → แทนที่ head ของ chain นั้น
4. จำนวน chains = คำตอบ

ตัวอย่างโค้ด C++

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

bool comp(const pair<int,int>& L, const pair<int,int>& R) {
    if (L.first == R.first) return L.second > R.second;
    return L.first < R.first;
}

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

int main() {
    vector<pair<int,int>> boxes = {{30,45},{15,15},{45,30},{60,75}};
    cout << Rectangles(boxes);
}

อินพุต

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

เอาต์พุท

2

Complexity

• Time: O(N log N) จาก sort + binary search
• Space: O(N)