GPU Task Scheduler: Memory-Constrained Combinations
Nvidia designs advanced GPUs and systems that power everything from AI research to high-performance computing. Efficient resource allocation is critical in these environments. This problem simulates a scenario where you need to schedule a set of GPU tasks, each with a specific memory footprint, within a finite memory budget. Finding all valid task groupings helps in optimizing system utilization, understanding resource limits, and planning future workloads.
Implement a function findTaskCombinations that, given an array of integers tasks (representing memory requirements) and an integer budget (total available memory), returns all unique combinations of tasks whose total memory requirement does not exceed budget.
[1, 2] is considered the same as [2, 1]). Your output should sort tasks within each combination in non-decreasing order.tasks = [2, 2, 3] and budget = 4, [[2], [2]] is not a valid output; instead, [[2], [2,2], [3]] is expected, where [2] and [2,2] represent combinations formed by distinct task instances). All single tasks that fit within the budget should also be included as valid combinations.tasks: An array of integers, where tasks[i] represents the memory requirement (in MB) for the i-th task. All tasks[i] will be positive.budget: An integer, representing the total available memory (in MB). budget will be positive.number[][] (array of arrays of numbers), where each inner array is a unique combination of task memory requirements that satisfies the conditions. The order of combinations in the outer array does not matter. The order of tasks within each inner array should be non-decreasing.tasks array should result in an empty number[][] array being returned.number[][] array should be returned.tasks array may contain duplicate memory requirements. These represent distinct tasks that happen to have the same memory footprint.Examples
Example 1
Input:
tasks = [1, 2, 3, 2], budget = 4
Output:
[[1,2], [1,3], [2], [2,2], [3]]
Note:
The tasks are sorted internally to [1, 2, 2, 3].
[1,2] using the second '2' is a duplicate of [1,2] using the first '2' and is excluded. Order of combinations and elements within combinations are normalized.Example 2
Input:
tasks = [5, 10, 15], budget = 10
Output:
[[5], [10]]
Note:
Only tasks with memory 5 and 10 fit individually. Any combination including 15, or a combination of 5 and 10, would exceed the budget.
Example 3
Input:
tasks = [1, 1, 1, 1], budget = 2
Output:
[[1], [1,1]]
Note:
With multiple tasks of memory 1 and a budget of 2, we can form combinations of [1] (using any single task) and [1,1] (using any two distinct tasks of memory 1). The output ensures uniqueness of combinations.
Constraints
1 <= tasks.length <= 201 <= tasks[i] <= 1001 <= budget <= 500tasks[i] and budget are positive integers.tasks array may contain duplicate memory requirements.Loading editor...