easyDynamic ProgrammingPattern: DP

Max Resource Allocation Solution

Problem Statement

Given a 2D array `resourceRequirements` where each sub-array represents the resource requirements for a habitat, and three integers `oxygen`, `water`, and `food` representing the total available resources, determine the maximum number of habitats that can be sustained with the available resources.

Examples

Example 1:

Input:[[1, 1, 1], [2, 2, 2], [3, 3, 3]], 10, 10, 10

Output:3

Explanation: Three habitats can be sustained with the available resources of 10 oxygen, 10 water, and 10 food.

Example 2:

Input:[[10, 10, 10], [20, 20, 20], [30, 30, 30]], 50, 50, 50

Output:2

Explanation: Only one habitat can be sustained with the available resources of 50 oxygen, 50 water, and 50 food.

Example 3:

Input:[[]], 10, 10, 10

Output:0

Explanation: No habitats can be sustained with the available resources of 10 oxygen, 10 water, and 10 food since the resourceRequirements array is empty.

Constraints

Resource requirements for each habitat are non-negative integers.
Available oxygen, water, and food resources are non-negative integers.
At least one of the available resources must be greater than zero.

Time: O(n log n) Space: O(n)

The optimized approach is to use a greedy algorithm that sorts the resource requirements and selects the habitats with the smallest resource requirements first.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

def max_resource_allocation(resource_requirements, oxygen, water, food):
    # Create copies to avoid modifying the original list
    resource_requirements_copy = resource_requirements.copy()
    remaining_resources = [oxygen, water, food]
    sustainable_habitats = 0

    # Sort the list of resource requirements by the oxygen requirement in ascending order
    resource_requirements_copy.sort(key=lambda x: x[0])

    # Iterate over each habitat's resource requirements
    for habitat_resources in resource_requirements_copy:
        if habitat_resources[0] <= remaining_resources[0] and habitat_resources[1] <= remaining_resources[1] and habitat_resources[2] <= remaining_resources[2]:
            # If the resources are sufficient, allocate the habitat and subtract the required resources
            sustainable_habitats += 1
            remaining_resources[0] -= habitat_resources[0]
            remaining_resources[1] -= habitat_resources[1]
            remaining_resources[2] -= habitat_resources[2]

    return sustainable_habitats