Optimal Utilization
MediumTwo Pointers · Amazon
A device has capacity units of memory and runs exactly one foreground app together with one background app. foreground and background are lists of apps, each given as [id, memory]. Ids are unique within each list.
Find the largest total foreground_memory + background_memory that does not exceed capacity, and return every [foreground_id, background_id] pair that achieves exactly that total.
Sort the returned pairs by foreground id, then by background id (both ascending). If no pair fits (including when either list is empty), return [].
Example 1
- Input:
- capacity = 10, foreground = [[1, 3], [2, 5], [3, 7]], background = [[1, 2], [2, 3], [3, 5], [4, 6]]
- Output:
- [[2, 3], [3, 2]]
- Explanation
- The largest total that fits is exactly 10, reached two ways: foreground 2 (5) with background 3 (5), and foreground 3 (7) with background 2 (3). Both pairs are returned, sorted by foreground id.
Example 2
- Input:
- capacity = 6, foreground = [[4, 4]], background = [[9, 3], [2, 1]]
- Output:
- [[4, 2]]
- Explanation
- 4 + 3 = 7 is over the capacity, so the best that fits is 4 + 1 = 5 with background app 2. The best total does not have to equal the capacity.
Example 3
- Input:
- capacity = 3, foreground = [[1, 2]], background = [[1, 2]]
- Output:
- []
- Explanation
- The only pair needs 4 units, which exceeds 3, so nothing fits.
Constraints
0 <= foreground.length, background.length <= 10^51 <= capacity <= 10^90 <= memory <= 10^9- Ids are unique within each list, and the number of returned pairs is at most
10^5