Pular para o conteúdo principal

Labeled Items Maximum Sum

You are given a list of values and a list of labels. The ith element in labels represents the label of the ith element. Similarly, the ith element in values represents the value associated with the ith element (i.e. together, an "item" could be thought of as a label and a price).

Given a list of values, a list of labels, a limit, and wanted, return the sum of the most expensive items you can group such that the total number of items used is less than wanted and the number of any given label that is used is less than limit.

Example(s)​

Example 1:

Input: 
  values = [5,4,3,2,1]
  labels = [1,1,2,2,3]
  wanted = 3
  limit = 1
Output: 9
Explanation: 
  We can select items at indices 0, 2, and 4:
  - Index 0: value 5, label 1
  - Index 2: value 3, label 2
  - Index 4: value 1, label 3
  Sum = 5 + 3 + 1 = 9
  Each label is used at most once (limit = 1), and we use 3 items (wanted = 3)

Example 2:

Input:
  values = [10,8,6,4,2]
  labels = [1,1,1,2,2]
  wanted = 3
  limit = 2
Output: 18
Explanation:
  We can select items at indices 0, 1, and 3:
  - Index 0: value 10, label 1
  - Index 1: value 8, label 1 (label 1 used twice, within limit)
  - Index 3: value 4, label 2
  Sum = 10 + 8 + 4 = 18

Solution​

The solution uses a greedy approach:

  1. Create pairs of (value, label, index) and sort by value in descending order
  2. Greedily select items while respecting constraints:
    • Track how many times each label has been used
    • Only select items if the label hasn't exceeded the limit
    • Stop when we've selected wanted items

JavaScript Solution

/**
* Find the maximum sum of items respecting label and count constraints
* @param {number[]} values - Array of item values
* @param {number[]} labels - Array of item labels
* @param {number} wanted - Maximum number of items to select
* @param {number} limit - Maximum number of items per label
* @return {number} - Maximum sum of selected items
*/
function maxSumLabeledItems(values, labels, wanted, limit) {
// Create array of items with their values, labels, and indices
const items = values.map((value, index) => ({
  value,
  label: labels[index],
  index
}));

// Sort by value in descending order (greedy: take most expensive first)
items.sort((a, b) => b.value - a.value);

// Track how many times each label has been used
const labelCount = new Map();
let sum = 0;
let selected = 0;

// Greedily select items
for (const item of items) {
  // Check if we've selected enough items
  if (selected >= wanted) {
    break;
  }
  
  // Check if this label has reached its limit
  const currentCount = labelCount.get(item.label) || 0;
  if (currentCount < limit) {
    // Select this item
    sum += item.value;
    labelCount.set(item.label, currentCount + 1);
    selected++;
  }
}

return sum;
}

// Test cases
console.log(maxSumLabeledItems([5,4,3,2,1], [1,1,2,2,3], 3, 1)); // 9
console.log(maxSumLabeledItems([10,8,6,4,2], [1,1,1,2,2], 3, 2)); // 18
console.log(maxSumLabeledItems([2,6,4,8], [2,2,2,2], 2, 1)); // 14 (8 + 6)
console.log(maxSumLabeledItems([1,2,3,4,5], [1,2,3,4,5], 5, 1)); // 15 (all items)
Output:
Click "Run Code" to execute the code and see the results.

Complexity​

  • Time Complexity: O(n log n) - Sorting the items by value dominates the time complexity
  • Space Complexity: O(n) - Space for storing items array and label count map

Approach​

The solution uses a greedy algorithm:

  1. Pair creation: Create tuples of (value, label, index) for each item
  2. Sorting: Sort items by value in descending order to prioritize expensive items
  3. Greedy selection: Iterate through sorted items and select them if:
    • We haven't selected wanted items yet
    • The label hasn't exceeded its limit
  4. Tracking: Use a map/dictionary to track how many times each label has been used

Key Insights​

  • Greedy approach works: Since we want to maximize the sum, always selecting the most expensive available item is optimal
  • Sorting is crucial: By sorting in descending order, we ensure we consider the most valuable items first
  • Constraint checking: We must check both the total count (wanted) and per-label count (limit) before selecting an item
  • Optimal substructure: The problem exhibits optimal substructure - selecting the best items at each step leads to the global optimum

Edge Cases​

  • When wanted is 0, return 0
  • When limit is 0, return 0 (can't select any items)
  • When all items have the same label and limit is less than wanted, we can only select limit items
  • When there are fewer items than wanted, we select all available items that respect the label constraints