Advantage Shuffle Algorithm

Everyone should be familiar with the story of Tian Ji's Horse Racing:

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

Of course, this historical episode is quite interesting. Zou Ji, who mocked King Qi for accepting advice and was extremely self-absorbed, lived during the same period as Tian Ji. They later clashed, but that's beside the point. Let's stop there.

When I learned about Tian Ji's horse racing in school, I wondered if it were not three horses but a hundred horses competing, could Sun Bin still arrange the racing order to win against King Qi?

At that time, I didn't come up with a good idea. I just felt that the core issue was to maximize one's own advantage and make the opponent suffer. In summary, fight if you can win, and if not, swap your weaker horses with the opponent's stronger ones.

However, I never implemented this idea concretely until recently when I encountered LeetCode problem #870 "Advantage Shuffle," which I immediately recognized as an enhanced version of Tian Ji's horse racing problem:

Given two equal-length arrays nums1 and nums2, you are asked to rearrange the elements in nums1 to maximize its "advantage."

If nums1[i] > nums2[i], it means nums1 has an "advantage" over nums2[i] at index i. Maximizing the advantage means rearranging 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!