Most Pairs of Similar Height
left and right list the heights of the dancers in two groups, in no particular order; the groups may have different sizes. A pair is one dancer from left and one from right whose heights differ by at most tolerance, and each dancer can be in at most one pair.
Return the largest number of pairs that can be formed. The largest number is unique, so no tie rule is needed. Return 0 when either list is empty.
Example 1
left [150,160,170]
right [155,175,162]
tolerance 5
returns 3
150 with 155, 160 with 162 and 170 with 175: every difference is at most 5.
Example 2
left [1,5,9]
right [2,3,10]
tolerance 1
returns 2
1 pairs with 2 and 9 with 10; 5 is more than 1 away from every dancer on the right.
Constraints
0 <= len(left) <= 1000 <= len(right) <= 1001 <= left[i], right[i] <= 10000 <= tolerance <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.