# Untitled

unknown
plain_text
a month ago
2.7 kB
3
Indexable
Never
```#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;
}```