# Optimal Utilization
###### tags: `Implementation`, `Array`, `Amazon OA`

Description:
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.

Solution:

public class OptimalUtilization {
    public List<int[]> OptimalUtilization(List<int[]> a, List<int[]> b, int target) {
        Collections.sort(a, (c, d) -> c[1] - d[1]);
        Collections.sort(b, (c, d) -> c[1] - d[1]);

        int l = 0;
        int r = b.size()- 1;
        int max = Integer.MIN_VALUE;
        List<int[]> res = new ArrayList<>();

        while (l < a.size() && r >= 0) {
            int sum = a.get(l)[1] + b.get(r)[1];
            if (sum > target) {
                r--;
            } else if (sum >= max) {
                if (sum > max) {
                    max = sum;
                    res.clear();
                }
                res.add(new int[]{a.get(l)[0], b.get(r)[0]});
                int p = r - 1;
                while (p >= 0 && b.get(p)[1] == b.get(p + 1)[1]) {
                    res.add(new int[]{a.get(l)[0], b.get(p)[0]});
                    --p;
                }
                l++;
            }
        }
        return res;
    }
}