โปรแกรม C++ หาจำนวนคู่พิกัดที่จับคู่ได้จากสองชุด

มีพิกัด 2n จุด แบ่งเป็น 2 ชุด coordA และ coordB (ขนาด n ต่อชุด) จับคู่ได้ก็ต่อเมื่อจุดจาก A มี x < x_B และ y < y_B จุดแต่ละจุดใช้ได้สูงสุด 1 คู่ หาจำนวนคู่สูงสุด

ตัวอย่าง: n=3, A={{1,3},{2,4},{4,3}}, B={{2,2},{4,2},{0,2}} ผลลัพธ์: 1 (คู่เดียวคือ (1,3) กับ (0,2) — หมายเหตุ: ตัวอย่างอาจมี typo ในเงื่อนไข)

ขั้นตอนการแก้ปัญหา (Greedy + Sorting)

1. เรียง coordA และ coordB (lexicographic)
2. อาร์เรย์ chk บอกว่า B[j] ใช้แล้วหรือยัง
3. วน A จากท้ายไปหน้า (ค่าใหญ่ไปเล็ก) สำหรับแต่ละ A[i] หา B[j] แรกที่ยังไม่ใช้ และ A[i].first < B[j].second และ A[i].second < B[j].first (หมายเหตุ: โค้ดใช้ first/second สลับกันในเงื่อนไข)
4. เจอ → mark chk[j]=1, k++, break
5. คืน k

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

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

#define N 100
void solve(int n, vector<pair<int,int>> coordA, vector<pair<int,int>> coordB) {
    int chk[100] = {0};
    sort(coordA.begin(), coordA.end());
    sort(coordB.begin(), coordB.end());
    int k = 0;
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            if (chk[j] == 0 && coordA[i].first < coordB[j].second && coordA[i].second < coordB[j].first) {
                chk[j] = 1; k++; break;
            }
        }
    }
    cout << k;
}

int main() {
    int n = 3;
    vector<pair<int,int>> coordsA = {{1,3},{2,4},{4,3}};
    vector<pair<int,int>> coordsB = {{2,2},{4,2},{0,2}};
    solve(n, coordsA, coordsB);
    return 0;
}

อินพุต / เอาต์พุต

Input: 3, {{1,3},{2,4},{4,3}}, {{2,2},{4,2},{0,2}}

Output: 1