Page Contents

Optimal Utilization 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.

See Also : Amazon Online Assessment Questions 2021 Preparation

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. Similarily, 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 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 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<>());
                    list.add(Arrays.asList(a[i][0], b[j][0]));
                }
            }
        }

        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 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))

Related:

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

Maximum Frequent Subarray Sum solution codechef
Dual Distance solution codechef
Optimal Xor Set solution codechef
Minimum Subtree Cover solution codechef
Minimum Dual Area solution codechef
Bitwise Tuples solution codechef
Shortest Route solution codechef
Bella ciao solution codechef
Summer Heat solution codechef

Optimal Utilization Solution Amazon OA 2021