Given two integer arrays
b and a map
m which for each element
e of the array
a returns an array
p of possible mappings, map every
a to an element
b so that
k, no element of
b is mapped twice and the number of non-mapped integers in
a is minimal. Note that both
b may have repetitive elements.
a = [1,2], b = [3,4], m = [1 => [3,4], 2 => ]
We see that 1 can be mapped both to 3 and to 4. However since we want the number of mapped elements to be maximal we must map 1 to 4 because 2 can only be mapped to 3. So the result here would be:
1 => 4, 2 => 3
So far I've only come up with the bruteforce solution which is to just try every possible mapping for every value in
a. However this solution has a time complexity of
O(n) = !n * k where
n is the number of elements in
k is the number of possible mappings.
How could you optimize this further to get the most efficient algorithm for solving the problem?