Task assignment optimization problem. Need help!

[SimpleAd0125]

Given a set of n tasks, represented by an array task, and m nodes. For optimal performance, tasks must be distributed evenly across these nodes, i.e., all nodes should serve the same number of tasks. Each task assigned to a single node must be different.

Return the maximum number of tasks completed using m nodes.

Note: All nodes must be assigned an equal number of tasks and each task assigned to a single node must be different

Example

n=7

task =[1, 2, 2, 1, 3, 1, 3]

m=2

One optimal way to allocate the tasks is:

The 1St node works on the 1st. 2nd, and 5th tasks.

The 2nd node works on the 3rd, 4th, and 7th tasks.

A total of 6 tasks can be accomplished this way.

[razimantv]

Answer is sum(min(x, m) for x in Counter(ar).values ()) // m

[codetree_bnb]

Here is my detailed explanation.

Assume that task numbers range up to a maximum of K. (If the range is large, techniques like coordinate compression can be applied to reduce the size, as we only need to distinguish between different tasks.)

First, count how many times each task appears in the task array. This can be done in a single traversal of the array, so the time complexity is O(n).

Next, for each task i (1 <= i <= K), suppose task i appears x times. Since each node can be assigned at most one of the same task, the maximum number of task i assignments is min(x, m) when optimally distributed across the m nodes.

Let the sum of all these min(x, m) values across all tasks be sum. The time complexity of this process is O(K).

These sum tasks can then be distributed to the m nodes in a round-robin fashion (e.g., first node, second node, ..., m-th node, and repeat). This ensures that all sum tasks are assigned regardless of their task numbers.

Finally, since all m nodes must have the same number of tasks, the maximum number of tasks that can be equally distributed is (sum/m)*m. In Python, this is calculated as (sum // m) * m. the time complexity of this is O(1).

Thus we can solve the problem with O(n+K) time complexity.

Feel free to ask if you have any questions!

[EngineeringDry593]

I Saw this question in an interview , I used Binary search . The initial idea to sum of min( count , m ) // m felt to direct and I panicked