Задача: 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⃣Верните итоговый результат.

😎 Решение:

public class Solution {
    public int[] AdvantageCount(int[] A, int[] B) {
        var sortedA = A.OrderBy(x => x).ToArray();
        var sortedB = B.Select((x, i) => new { Value = x, Index = i }).OrderBy(x => x.Value).ToArray();
        var assigned = new Dictionary<int, Queue<int>>();
        var remaining = new Queue<int>();
        int j = 0;

        foreach (var a in sortedA) {
            if (a > sortedB[j].Value) {
                if (!assigned.ContainsKey(sortedB[j].Value))
                    assigned[sortedB[j].Value] = new Queue<int>();
                assigned[sortedB[j].Value].Enqueue(a);
                j++;
            } else {
                remaining.Enqueue(a);
            }
        }

        var result = new int[B.Length];
        for (int i = 0; i < B.Length; i++) {
            if (assigned.ContainsKey(B[i]) && assigned[B[i]].Count > 0) {
                result[i] = assigned[B[i]].Dequeue();
            } else {
                result[i] = remaining.Dequeue();
            }
        }

        return result;
    }
}

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