0
\$\begingroup\$

I came across this problem in a programming challenge a few days ago. I came up with the implementation below, however it resulted in a "time limit exceeded" failure for a few of the test cases. The questions were unfortunately not made available after the challenge was over but it went something like this:

There are a number of CPUs that each have a number of jobs already assigned to them. The CPUs are represented as an integer array cpus where cpus[i] represents the number of jobs currently assigned to the \$ith\$ CPU. You are given a number of additional jobs to assign to the CPUs. The goal is to assign the new jobs to the CPUs in a way that minimizes the difference between the CPU with the maximum number of jobs assigned and the CPU with the minimum number of jobs assigned. All jobs must be assigned to a CPU. Jobs that have been assigned to a CPU cannot be reassigned to a different CPU.

The constraints were all quite large, something like:

  • \$1 <= cpus.Length <= 10^6\$
  • \$0 <= cpus[i] <= 10^6\$
  • \$1 <= jobs <= 10^9\$

The only way that I could visualize a solution was to first sort the array, and then fill in the jobs iteratively working from the smallest array elements up. Basically "pouring" the jobs into the lower void of the array and filling it up as if it were being filled with a liquid until all the array values were equal (or all jobs have been distributed). Evidently there is a faster way to do this!

int MaxDifference(int[] cpus, int jobs) {

    // Sort the array in ascending order.
    Array.Sort(cpus);
    
    // Get the initial min/max values.
    var min = cpus[0];
    var max = cpus[cpus.Length - 1];
    
    // Distribute the jobs over the CPUs until all jobs are allocated or all CPUs have an equal number of jobs.
    var i = 0;
    while (jobs > 0 && min < max) {
        
        // Distribute a job to the current CPU.
        cpus[i]++;
        jobs--;
        
        // Advance to the next CPU if it has fewer jobs than the current one or start over at the beginning.
        if (i < cpus.Length - 1 && cpus[i + 1] < cpus[i]) {
            i++;
        } else {
            i = 0;
        }
        
        // Update the new min value.
        min = cpus[i];
    }
    
    // Check to see which condition halted our distribution loop.
    if (jobs > 0) {
    
        // Since all CPUs have an equal number of jobs the max difference can only be 0 or 1.
        return jobs % cpus.Length == 0 ? 0 : 1;
    } else {
    
        // Since all jobs have been allocated just return the difference between the max and the min.
        return max - min;
    }
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

This is not a proper review, but an extended comment.

Your visualization is correct. The time complexity problem stems from the way the jobs are poured. You pour them one at a time. You may do better pouring them in rounds.

Let \$c_i\$ be a number of jobs at \$i_{th}\$ cpu after sorting.

The goal of the first round is to equalize \$c_0\$ and \$c_1\$. It takes \$c_1 - c_0\$ jobs.

The goal of the second round is to equalize \$c_0, c_1, c_2\$ it tales \$2 (c_2 - c1)\$ jobs (\$c_0\$ is already equal to \$c_1\$.

In general. the \$k_{th}\$ round, equalizing everything to \$c_k\$, takes \$k (c_k - c_{k-1})\$ jobs.

This observation hints a solution: cumulatively compute \$\sum_{k=1} k(c_k - c_{k-1})\$ for as long as it is less than the amount of jobs. The resulting time complexity is linear in the number of CPUs; of course the sorting phase would dominate.

\$\endgroup\$
1
  • \$\begingroup\$ This is exactly what I was looking for, thanks! So much more elegant this way. One small note for anyone else reading: Because the CPU array is not guaranteed to contain only unique values the first round might be something like c4 - c3 in the case of an array like [1, 1, 1, 1, 2, 4] instead of c1 - c0. \$\endgroup\$ Apr 7, 2022 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.