# Optimal Utilization Amazon OA 2023

## Optimal Utilization Amazon OA 2023 Solution

Given 2 lists a and b. Each element is a pair of integers where the first integer represents the unique id and the second integer represents a value. Your task is to find an element from a and an element form b such that the sum of their values is less or equal to target and as close to target as possible. Return a list of ids of selected elements. If no pair is possible, return an empty list.

Example 1:

Input:

a = [[1, 2], [2, 4], [3, 6]]

b = [[1, 2]]

target = 7

Output: [[2, 1]]

Explanation:

• There are only three combinations [1, 1], [2, 1], and [3, 1], which have a total sum of 4, 6 and 8, respectively.
• Since 6 is the largest sum that does not exceed 7, [2, 1] is the optimal pair.

Example 2:

Input:

a = [[1, 3], [2, 5], [3, 7], [4, 10]]

b = [[1, 2], [2, 3], [3, 4], [4, 5]]

target = 10

Output: [[2, 4], [3, 2]]

Explanation:

• There are two pairs possible. Element with id = 2 from the list `a` has a value 5, and element with id = 4 from the list `b` also has a value 5.
• Combined, they add up to 10. Similarly, element with id = 3 from `a` has a value 7, and element with id = 2 from `b` has a value 3. These also add up to 10. Therefore, the optimal pairs are [2, 4] and [3, 2].

Example 3:

Input: a = [[1, 8], [2, 7], [3, 14]]

b = [[1, 5], [2, 10], [3, 14]]

target = 20

Output: [[3, 1]]

Example 4:

Input: a = [[1, 8], [2, 15], [3, 9]]

b = [[1, 8], [2, 11], [3, 12]]

target = 20

Output: [[1, 3], [3, 2]]

### SOLUTION

Program: Optimal Utilization Solution in C++

``````#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;
vector<vector<int>> optimal(vector<vector<int>>& a, vector<vector<int>>& b, int target)
{
std::sort(a.begin(), a.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1];});
std::sort(b.begin(), b.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1];});
auto aptr = a.begin();
auto bptr = b.rbegin();
int minSum = -1 * __INT_MAX__;
vector<vector<int>> res;
while(aptr != a.end() && bptr != b.rend())
{
int sum = (*aptr)[1] + (*bptr)[1];
if(sum > target)
{
//decrement bptr
++bptr;
}
else
{
//sum <= to target which is what we want
if(sum > minSum)
{
res.clear();
}
res.push_back({(*aptr)[0], (*bptr)[0]});
minSum = sum;
++aptr;
}
}
return res;
}
void test(vector<vector<int>> a, vector<vector<int>> b, int target)
{
vector<vector<int>> res = optimal(a, b, target);
for(auto i = res.begin(); i != res.end(); ++i)
{
for(auto j = (*i).begin(); j != (*i).end(); ++j)
cout << ' ' << *j;
cout << '\n';
}
cout << endl;
}
int main()
{
test({{1, 2}, {2, 4}, {3, 6}}, {{1, 2}}, 7);
test({{1, 3}, {2, 5}, {3, 7}, {4, 10}}, {{1, 2}, {2, 3}, {3, 4}, {4, 5}}, 10);
test({{1, 8}, {2, 7}, {3, 14}}, {{1, 5}, {2, 7}, {3, 14}}, 20);
return 0;
}``````

Program: Optimal Utilization Solution in Java

``````import java.util.*;
public class OptimalUti {
private static List<List<Integer>> compute(int[][] a, int[][] b, int target) {
List<List<Integer>> res = new ArrayList<>();
TreeMap<Integer, List<List<Integer>>> tree = new TreeMap<>();
for (int i=0; i<a.length; i++) {
for (int j=0; j<b.length; j++) {
int sum = a[i][1] + b[j][1];
if (sum <= target) {
List<List<Integer>> list = tree.computeIfAbsent(sum, (k) -> new ArrayList<>());
}
}
}
return tree.floorEntry(target).getValue();
}
public static void main(String...s) {
int[][][] As = {
{{1, 2}, {2, 4}, {3, 6}},
{{1, 3}, {2, 5}, {3, 7}, {4, 10}},
{{1, 8}, {2, 7}, {3, 14}},
{{1, 8}, {2, 15}, {3, 9}}
};
int[][][] Bs = {
{{1, 2}},
{{1, 2}, {2, 3}, {3, 4}, {4, 5}},
{{1, 5}, {2, 10}, {3, 14}},
{{1, 8}, {2, 11}, {3, 12}}
};
int[] targets = {7, 10, 20, 20};
for (int i=0; i<4; i++) {
System.out.println(compute(As[i], Bs[i], targets[i]).toString());
}
}
}``````

Program: Optimal Utilization Solution in Python

``````def find_element(nums, target):
length = len(nums)
st = 0
ed = length-1
while st < ed:
mid = (st + ed + 1) // 2
if nums[mid][1] > target:
ed = mid - 1
else:
st = mid
return nums[st]
def UptimalUtilization(a, b, target):
a.sort(key=lambda x:x[1])
b.sort(key=lambda x:x[1])
len1 = len(a)
len2 = len(b)
curval = 0
res = []
for idx1, num1 in a:
idx2, num2 = find_element(b,target-num1)
if num1 + num2 <= target:
print(num1+num2)
if curval < num1 + num2:
curval = num1 + num2
res = [[idx1, idx2]]
elif curval == num1 + num2:
res.append([idx1, idx2])
return res
a = [[1, 2], [2, 4], [3, 6]]
b = [[1, 2]]
target = 7
print(UptimalUtilization(a, b, target))``````