Задача: 870. Advantage Shuffle
Сложность: medium

Даны два целочисленных массива nums1 и nums2 одинаковой длины. Преимущество nums1 относительно nums2 — это количество индексов i, для которых nums1[i] > nums2[i].

Верните любую перестановку nums1, которая максимизирует его преимущество относительно nums2.

Пример:

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

👨‍💻 Алгоритм:

1⃣Отсортируйте nums1 и nums2. Для каждой карты a из отсортированного nums1 определите, может ли она побить текущую наименьшую карту b из отсортированного nums2. Если да, добавьте a в assigned[b], если нет, добавьте a в remaining.

2⃣После распределения всех карт из nums1, используйте assigned и remaining для построения итогового результата. Для каждой карты b из nums2, если assigned[b] не пуст, добавьте в результат последнюю карту из assigned[b], иначе добавьте последнюю карту из remaining.

3⃣Верните итоговый результат.

😎 Решение:

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> sortedA(A);
        sort(sortedA.begin(), sortedA.end());
        vector<pair<int, int>> sortedB;
        for (int i = 0; i < B.size(); ++i)
            sortedB.push_back({B[i], i});
        sort(sortedB.begin(), sortedB.end());

        unordered_map<int, deque<int>> assigned;
        for (int b: B) assigned[b] = {};

        deque<int> remaining;
        int j = 0;
        for (int a: sortedA) {
            if (a > sortedB[j].first) {
                assigned[sortedB[j++].first].push_back(a);
            } else {
                remaining.push_back(a);
            }
        }

        vector<int> ans(B.size());
        for (int i = 0; i < B.size(); ++i) {
            if (assigned[B[i]].size() > 0) {
                ans[i] = assigned[B[i]].front();
                assigned[B[i]].pop_front();
            } else {
                ans[i] = remaining.front();
                remaining.pop_front();
            }
        }
        return ans;
    }
};

Ставь 👍 и забирай 📚 Базу знаний