เพิ่มจำนวน Unique Pairs จากสองอาร์เรย์ใน C++

โจทย์

ได้รับอาร์เรย์สองอันขนาดเท่ากัน N สร้างคู่ (Pair) จำนวนมากที่สุดโดยใช้องค์ประกอบ หนึ่งจากอาร์เรย์แรก และอีกหนึ่งจากอาร์เรย์ที่สอง โดยที่องค์ประกอบจากแต่ละอาร์เรย์ถูกใช้ได้สูงสุด 1 ครั้ง และค่าสัมบูรณ์ของความต่างระหว่างองค์ประกอบที่เลือกต้องน้อยกว่าหรือเท่ากับ K ที่กำหนด

ตัวอย่าง

ถ้าอินพุตคือ

arr1[] = {3, 4, 5, 2, 1}

arr2[] = {6, 5, 4, 7, 15}

และ k = 3 แล้วสามารถสร้าง 4 คู่ที่ความต่างสัมบูรณ์ ≤ 3 ได้ดังนี้

(1, 4), (2, 5), (3, 6), (4, 7)

อัลกอริทึม

ใช้วิธี Recursive/Greedy เพื่อแก้ปัญหานี้

• จัดเรียงทั้งสองอาร์เรย์
• เปรียบเทียบแต่ละองค์ประกอบของอาร์เรย์แรกกับอาร์เรย์ที่สองเพื่อหาคู่ที่เป็นไปได้
• ต่อไปตรวจสอบคู่ถัดไปสำหรับองค์ประกอบถัดไปของอาร์เรย์แรก

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

#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);
    bool visited[n];
    memset(visited, false, sizeof(visited));
    int pairCnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (abs(arr1[i] - arr2[j]) <= k && visited[j] == false) {
                ++pairCnt;
                visited[j] = true;
                break;
            }
        }
    }
    return pairCnt;
}

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 << "Maximum unique pairs = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;
    return 0;
}

ผลลัพธ์

Maximum unique pairs = 4