Tối đa hóa số cặp duy nhất từ hai mảng trong C++

Đề bài

Cho hai mảng cùng kích thước N. Tạo nhiều cặp nhất có thể (mỗi cặp lấy một phần tử từ mỗi mảng), mỗi phần tử dùng tối đa một lần, sao cho hiệu tuyệt đối của hai phần tử ≤ K.

Ví dụ: A={3,4,5,2,1}, B={6,5,4,7,15}, K=3 → 4 cặp: (1,4),(2,5),(3,6),(4,7).

Thuật toán (Tham lam sau khi sắp xếp)

1. Sắp xếp cả hai mảng tăng dần.
2. Duyệt mảng A, với mỗi phần tử tìm phần tử đầu tiên trong B chưa dùng sao cho |A[i]-B[j]| ≤ K.
3. Đánh dấu B[j] đã dùng, tăng đếm cặp.

Ví dụ minh họa (C++)

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

int getMaxUniquePairs(int* arr1, int* arr2, int n, int k) {
    sort(arr1, arr1 + n);
    sort(arr2, arr2 + n);
    vector<bool> used(n, false);
    int pairs = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (!used[j] && abs(arr1[i] - arr2[j]) <= k) {
                ++pairs;
                used[j] = true;
                break;
            }
        }
    }
    return pairs;
}

int main() {
    int arr1[] = {3, 4, 5, 2, 1};
    int arr2[] = {6, 5, 4, 7, 15};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int k = 3;
    cout << "So cap duy nhat toi da = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;
    return 0;
}

Kết quả

So cap duy nhat toi da = 4