Find a pair of entries from two lists that yield a sum that is as close to a target number as possible, without exceeding it.
Each entry in a list is a key-value pair, where the key is a number identifier and the value is also a number. The output must be a list containing the pairs of numbers representing the identifiers that yield the result.
If a solution is not possible, return an empty list.
Notice the input could be not sorted.
Example 1:
Input:
a = [12, 14, 16], b = [2], target = 17,
Output: [[1, 0]]
Explanation:
There are only three possible pairs, [0, 0], [1, 0], and [2, 0]. They yield the sum values of 12 + 2 = 14, 14 + 2 = 16 and 16 + 2 = 18 respectively.
16 is the largest number that does not exceed 17, therefore [1, 0] is the optimal pair.
Example 2:
Input:
a = [3, 5, 7, 10], b = [2, 3, 4, 5], target = 10,
Output: [[1, 3], [2, 1]]
Explanation:
There are two pairs possible. The element with id = 1 from list a has a value of 5, and the element with id = 3 from list b also has a value of 5. Combined, they add up to 10.
Likewise, the element with id = 2 from a has a value of 7, and the element with id = 1 from b has a value of 3. These also add up to 10.
Therefore, the optimal pairs are [1, 3] and [2, 1].
Example 3:
Input:
a = [8, 7, 14], b = [5, 10, 14], target = 20,
Output: [[2, 0]]