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; }
Leave a Comment