Untitled

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> applicationPairs(int deviceCapacity, vector<vector<int>>& foregroundAppList, vector<vector<int>>& backgroundAppList) {
    vector<vector<int>> result;
    int maxUtilization = 0;

    // Sort the lists based on memory usage
    sort(foregroundAppList.begin(), foregroundAppList.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; });
    sort(backgroundAppList.begin(), backgroundAppList.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; });

    int i = 0, j = backgroundAppList.size() - 1;

    // Two-pointer technique to find the optimal pairs
    while (i < foregroundAppList.size() && j >= 0) {
        int sum = foregroundAppList[i][1] + backgroundAppList[j][1];

        if (sum <= deviceCapacity) {
            // If the current sum is better than previous best, clear the result list
            if (sum > maxUtilization) {
                maxUtilization = sum;
                result.clear();
            }
            // If the sum equals the max utilization, store the pair
            if (sum == maxUtilization) {
                result.push_back({foregroundAppList[i][0], backgroundAppList[j][0]});
            }
            i++; // Try to increase the sum by moving the foreground pointer
        } else {
            j--; // Decrease the sum by moving the background pointer
        }
    }

    return result;
}

int main() {
    // Example 1
    int deviceCapacity1 = 7;
    vector<vector<int>> foregroundAppList1 = {{1, 2}, {2, 4}, {3, 6}};
    vector<vector<int>> backgroundAppList1 = {{1, 2}};
    vector<vector<int>> result1 = applicationPairs(deviceCapacity1, foregroundAppList1, backgroundAppList1);
    for (auto& pair : result1) {
        cout << "[" << pair[0] << ", " << pair[1] << "] ";
    }
    cout << endl;

    // Example 2
    int deviceCapacity2 = 10;
    vector<vector<int>> foregroundAppList2 = {{1, 3}, {2, 5}, {3, 7}, {4, 10}};
    vector<vector<int>> backgroundAppList2 = {{1, 2}, {2, 3}, {3, 4}, {4, 5}};
    vector<vector<int>> result2 = applicationPairs(deviceCapacity2, foregroundAppList2, backgroundAppList2);
    for (auto& pair : result2) {
        cout << "[" << pair[0] << ", " << pair[1] << "] ";
    }
    cout << endl;

    // Example 3
    int deviceCapacity3 = 16;
    vector<vector<int>> foregroundAppList3 = {{2, 7}, {3, 14}};
    vector<vector<int>> backgroundAppList3 = {{7, 10}, {3, 14}};
    vector<vector<int>> result3 = applicationPairs(deviceCapacity3, foregroundAppList3, backgroundAppList3);
    for (auto& pair : result3) {
        cout << "[" << pair[0] << ", " << pair[1] << "] ";
    }
    cout << endl;

    return 0;
}