Advantage Shuffle Algorithm

The story of Tian Ji's horse racing is well-known:

Tian Ji and the King of Qi raced horses, with their horses divided into upper, middle, and lower grades. If horses of the same grade raced against each other, Tian Ji couldn't win. However, Tian Ji met Sun Bin, who advised him to use his lower-grade horse against the King's upper-grade horse, his upper-grade horse against the King's middle-grade horse, and his middle-grade horse against the King's lower-grade horse. As a result, Tian Ji won two out of three races.

Of course, this historical anecdote is quite interesting. Zou Ji, who criticized the King of Qi and was extremely self-absorbed, lived during the same period as Tian Ji, and they later became rivals. But that's beside the point; we'll stop here.

When I first learned about Tian Ji's horse racing in school, I wondered: if it weren't three horses racing but a hundred, could Sun Bin still arrange the order of races to win against the King of Qi?

At the time, I couldn't come up with a good solution, but I realized the core problem was to maximize one's own advantage while minimizing the opponent's. In summary, fight when you can win, and trade your weakest against the opponent's strongest when you can't.

However, I never implemented this idea until recently when I came across LeetCode problem 870, "Advantage Shuffle", and immediately recognized it as an enhanced version of Tian Ji's horse racing problem:

You are given two equal-length arrays nums1 and nums2. You need to reorganize the elements of nums1 to maximize its "advantage" over nums2.

If nums1[i] > nums2[i], it means nums1 has an "advantage" over nums2[i] at index i. Maximizing the advantage means reorganizing nums1 to make as many nums1[i] > nums2[i] as possible.

The algorithm signature is as follows:

int[] advantageCount(int[] nums1, int[] nums2);

vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2);

def advantageCount(nums1: List[int], nums2: List[int]) -> List[int]:

func advantageCount(nums1 []int, nums2 []int) []int {}

var advantageCount = function(nums1, nums2) {}

For example, given the input:

nums1 = [12,24,8,32]
nums2 = [13,25,32,11]

Your algorithm should return [24,32,8,12], because arranging nums1 in this way gives three elements the "advantage".

This is similar to the scenario in the story of "Tian Ji's Horse Racing". nums1 represents Tian Ji's horses, nums2 represents King Qi's horses, and the elements in the arrays represent the horses' combat power. You are Sun Bin, show your true skills!