Amazon Online Assessment (OA) - Optimize Memory Usage

Given a computer with a total of K memory space, and an array of foreground tasks and background tasks the computer needs to do.

Write an algorithm to find a pair of tasks from each array to maximize memory usage.

Notice that the tasks can be done without original order.

Input

The input consists of five arguments:

foregroundTask: an array representing the memory usage of the foreground tasks

backgroundTask: an array representing the memory usage of the background tasks

K: the total memory space of the computer

Output

Return a list of pairs of the task ids.

Examples

Example 1:

Input:

foregroundTasks = [1, 7, 2, 4, 5, 6]

backgroundTasks = [3, 1, 2]

K = 6

Output: [[3, 2], [4, 1], [5,-1]]

Explanation:

Here we have 5 foreground tasks:

• Task 0 uses 1 memory.
• Task 1 uses 7 memory.
• Task 2 uses 2 memory.

5 background tasks:

• Task 0 uses 3 memory.
• Task 1 uses 1 memory.
• Task 2 uses 2 memory.

We need to find two tasks with total memory usage sum <= K.

Here we can return the foreground task 3 and background task 2, which total use 6 units of memory. Or we can return the foreground task 4 and background task 1. Also, use total 6 units of memory. Or we can return the foreground task 5 only without any background task. Also, use total 6 units of memory.

Example 2:

Input:

foregroundTasks = [1, 7, 2, 4, 5, 6]

backgroundTasks = [1, 1, 2]

K = 10

Output: [[1, 2]]

Explanation:

Here we can return the foreground task 1 and background task 2:

Total memory usage is 7 + 2 = 9, which is smaller than 10.

Given there is no larger better memory usage combination than 9, this is the optimal solution.

Try it yourself