Unique Gift Packing

Moderate

0/80

1 upvote

Problem statement

You are a gift packer preparing for a large event. You are given an array items of size N, where each element represents a type of gift. You need to select a collection of gifts to pack based on a special set of rules.

The rules for packing are:

You can choose to include any number of available gift types.

For each type of gift you choose to pack, you can take one or more items of that type, up to the total number available.

The number of items you pack for each selected type (its "packed frequency") must be unique. For example, you cannot pack 5 items of type 'A' and also 5 items of type 'B'.

Your goal is to maximize the total number of individual items packed. Return this maximum number..

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer N, the total number of items available.
The second line contains N space-separated integers, representing the types of the available items.

Output Format:

The output should be a single integer representing the maximum total number of items that can be packed according to the rules.

Note:

The first step is to count the frequency of each type of gift available.
The problem then becomes selecting a unique, positive "packed frequency" for each gift type, such that the packed frequency is less than or equal to its available frequency, and the sum of these packed frequencies is maximized.
A greedy approach is effective: process the gift types from most frequent to least frequent. For each type, try to pack as many items as possible (up to its available frequency) while ensuring the packed frequency has not been used by another type.

Sample Input 1:

6
1 2 2 3 3 3

Sample Output 1:

Explanation for Sample 1:

Type 3 (3 available): We can pack 3 items. The frequency 3 has not been used yet. Total packed = 3. Used frequencies: {3}.
Type 2 (2 available): We can pack 2 items. The frequency 2 has not been used. Total packed = 3 + 2 = 5. Used frequencies: {3, 2}.
Type 1 (1 available): We can pack 1 item. The frequency 1 has not been used. Total packed = 5 + 1 = 6. Used frequencies: {3, 2, 1}.
The maximum number of items is 6.

Expected Time Complexity:

The expected time complexity is O(N + U log U), where N is the number of items and U is the number of unique item types.

Constraints:

1 <= N <= 10^5
1 <= items[i] <= 10^9
Time limit: 1sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Unique Gift Packing

Console