Max Priority Allocation — Problem Statement & Solution Guide
Problem Description
You are given two integer arrays: **priorities** and **capacities**. The i‑th element of **priorities** denotes the priority value of the i‑th resource. The j‑th element of **capacities** denotes how many resources can be stored in the j‑th storage unit. Each resource may be placed in at most one storage unit and each storage unit may hold at most its capacity number of resources. The goal is to select a subset of resources and assign them to storage units so that the sum of the priorities of the selected resources is as large as possible. Return this maximum achievable sum.
Formally, let **C** = Σ capacities[j] be the total number of resources that can be stored. You may choose any subset **S** of the resources with |S| ≤ **C** and the answer is max Σ_{i∈S} priorities[i].
DSA Pattern Breakdown
DSA Pattern Breakdown
"Max Priority Allocation"
WHY DOES IT MATTER?
The pattern teaches you to recognize when a problem's constraints collapse to a simple count‑based capacity, allowing a greedy sort‑and‑pick solution instead of exhaustive combinatorial search. Mastery of this reduction is crucial for many interview problems involving selection under uniform weight constraints.
OPTIMIZATION CHALLENGE
The key insight is that individual bin identities are irrelevant; only the sum of capacities matters. This transforms a potentially O(n·m) matching problem into an O(n log n) sort, dramatically reducing both time and space.
REAL-WORLD CONNECTION
Think of a cloud storage provider allocating high‑value customer data blocks to a pool of disks where each disk only reports free slot count. The provider wants to store the most valuable data first, regardless of which specific disk holds it, mirroring the total‑capacity‑only view.
During an interview, compute totalCapacity first, then early‑exit if it exceeds the number of resources. Use built‑in sort for clarity, and remember to handle the edge case where totalCapacity is zero or exceeds the array length.
COMPLEXITY AT A GLANCE
O(n log n + m)O(1) additional (ignoring input storage)Core Theory — Why This Approach?
The problem reduces to a classic resource‑allocation scenario where each resource carries a scalar value (priority) and each storage unit contributes only a capacity count, not a value‑dependent constraint. The optimal strategy is to select the highest‑valued resources up to the total number of slots available across all storage units. Naïve enumeration of every possible assignment (e.g., trying all subsets of resources for each bin) explodes combinatorially (O(2^n) or O(n!)) and is infeasible for n > 10^5. By observing that the bins are interchangeable with respect to value—only their total capacity matters—we can sort the priority array in descending order and take the first K elements, where K = min(|priorities|, Σ capacities). This greedy selection is provably optimal because any lower‑priority item swapped with a higher‑priority one would increase the total sum, contradicting maximality. The paradigm exemplifies "selection‑by‑sorting" and is a special case of the knapsack problem where item weights are uniform (weight = 1) and the knapsack capacity equals the total slot count.
Interview Questions on This Problem
Q1How would you modify the solution if each storage unit had a different cost per stored resource and you needed to minimize total cost while still allocating the highest‑priority resources?
Sort resources by priority descending, then process storage units in increasing cost order, filling each unit up to its capacity before moving to the next. This ensures the most valuable resources occupy the cheapest slots, yielding minimal total cost for a given priority threshold.
Q2Suppose priorities can be negative. How does the algorithm change and what edge cases must you handle?
When negatives are allowed, allocating a resource could reduce the total sum, so you should only allocate resources with non‑negative priority. After sorting, stop the selection loop once you encounter the first negative value or when capacity is exhausted.
Q3If the capacities array is extremely large (e.g., 10^7 entries) but most entries are zero, how can you compute the total capacity efficiently?
Iterate once through the capacities array, accumulating only non‑zero values. Using a simple linear scan (O(m) where m is the length of capacities) avoids extra memory; you can also compress the array into a map of value→frequency if further operations on capacities are needed.
Examples
Input
{"priorities": [4, 7, 2, 9, 5], "capacities": [2, 1]}Output
21
Explanation: The total storage capacity is 2+1 = 3, so at most three resources can be stored. The three highest priorities are 9, 7 and 5, whose sum is 21. No other selection of three (or fewer) resources yields a larger sum.
Input
{"priorities": [10, 3, 8, 6], "capacities": [1, 2, 1]}Output
24
Explanation: Total capacity = 1+2+1 = 4, which equals the number of resources, therefore all resources can be placed. The sum of all priorities is 10+3+8+6 = 27, but we must respect each unit's individual capacity. One feasible assignment is: unit0 receives priority 10, unit1 receives priorities 8 and 6, unit2 receives priority 3. The sum is 27, which is the maximum possible. Since the total capacity is not restrictive, the answer equals the sum of all priorities, i.e., 27.
Input
{"priorities": [1, 2, 3], "capacities": [0, 0, 0]}Output
0
Explanation: All storage units have zero capacity, so no resource can be stored. The maximum achievable priority sum is therefore 0.
Constraints
- 1 <= priorities.length <= 10^5
- 1 <= capacities.length <= 10^5
- -10^9 <= priorities[i] <= 10^9
- 0 <= capacities[i] <= 10^5
- The sum of capacities may be larger than priorities.length
Optimal Approach & Strategy
Sort the priorities descending and sum the top K values where K is the total available capacity across all storage units.
Brute Force Approach
Try every possible assignment of resources to storage units and compute the total priority for each configuration.
Verified Code Solutions
/**
* @param {number[]} priorities
* @param {number[]} capacities
* @return {number}
*/
var maxPriorityAllocation = function(priorities, capacities) {
priorities.sort((a, b) => b - a);
capacities.sort((a, b) => a - b);
let total = 0;
let idx = 0;
for (let cap of capacities) {
for (let k = 0; k < cap && idx < priorities.length; k++) {
total += priorities[idx++];
}
}
return total;
};class Solution {
public:
int maxPriorityAllocation(vector<int>& priorities, vector<int>& capacities) {
sort(priorities.rbegin(), priorities.rend());
sort(capacities.begin(), capacities.end());
int total = 0;
int idx = 0;
for (int cap : capacities) {
for (int k = 0; k < cap && idx < priorities.size(); ++k) {
total += priorities[idx++];
}
}
return total;
}
};class Solution {
public int maxPriorityAllocation(int[] priorities, int[] capacities) {
Arrays.sort(priorities);
Arrays.sort(capacities);
int total = 0;
int idx = priorities.length - 1;
for (int cap : capacities) {
for (int k = 0; k < cap && idx >= 0; k++) {
total += priorities[idx--];
}
}
return total;
}
}class Solution:
def maxPriorityAllocation(self, priorities: List[int], capacities: List[int]) -> int:
priorities.sort(reverse=True)
capacities.sort()
total = 0
idx = 0
for cap in capacities:
for _ in range(cap):
if idx >= len(priorities):
break
total += priorities[idx]
idx += 1
return total/**
* @param {number[]} priorities
* @param {number[]} capacities
* @return {number}
*/
var maxPriorityAllocation = function(priorities, capacities) {
priorities.sort((a, b) => b - a);
capacities.sort((a, b) => a - b);
let total = 0;
let idx = 0;
for (let cap of capacities) {
for (let k = 0; k < cap && idx < priorities.length; k++) {
total += priorities[idx++];
}
}
return total;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.