mediumArraysPattern: Two Pointers

Max Crates Allocation Solution

Problem Statement

Given two arrays, `crateWeights` and `teamCapacities`, determine the maximum number of crates that can be distributed among the teams such that the total weight of crates assigned to each team does not exceed its capacity.

Examples

Example 1:

Input:[1, 2, 3, 4, 5], [10, 15, 20]

Output:5

Explanation: Assign the crate with weight 5 to the team with capacity 20. Then, assign the crates with weights 4 and 3 to the remaining capacity of the team with capacity 20 and the team with capacity 15 respectively, but it is possible to assign crates of weights 1 and 2 to the first team as well.

Example 2:

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

Output:3

Explanation: Teams can take crates with weights 10 and 20, totaling 30, and crate with weight 30, totaling 30, without exceeding the capacity of either team.

Example 3:

Input:[5, 5, 5, 5], [5, 5, 5]

Output:3

Explanation: Each team can take one crate with weight 5.

Constraints

0 <= crateWeights.length <= 100000
0 <= crateWeights[i] <= 10^5
0 <= teamCapacities.length <= 100000
0 <= teamCapacities[i] <= 5 * 10^5

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

Use dynamic programming and sorting to find the optimal solution in O(n log n) time complexity.

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_crates_allocation(crate_weights, team_capacities):
    crate_weights.sort(reverse=True)
    team_capacities.sort(reverse=True)
    i, j, count = 0, 0, 0
    while i < len(crate_weights) and j < len(team_capacities):
        if crate_weights[i] <= team_capacities[j]:
            count += 1
            i += 1
            j += 1
        else:
            j += 1
    return count