1
$\begingroup$

I was doing the HackerRank Coding Challenge and ran into this problem. I thought through it a bit but wasn't able to come up with a concrete solution, and going through the solution was not very helpful as I don't understand the reasoning behind it. Here is the prompt:

The computing cluster has multiple processors, each with 4 cores. The number of tasks to handle is equal to the total number of cores in the cluster. Each task has a predicted execution time and each processor has a specified time when its core becomes available. Assuming that exactly 4 tasks are assigned to each processor and those tasks run independently(asynchronously) on the cores of the chosen processor, what is the earliest time that all tasks can be processed.

Example

n = 2

processorTime = [8, 10]

taskTime = [2, 2, 3, 1, 8, 7, 4, 5]

One optimal solution is as follows:

Assign the tasks with the execution times 2, 3, 7, and 8 to processor 0 that start at time 8.

Assign the tasks with the execution times 4, 2, 5, and 1 to processor 1 that start at time 10.

The first processor's cores finish at times (8+2), (8+3), (8+7), and (8+8), which are 10, 11, 15, and 16 respectively.

The second processor's cores finish at times (10+4), (10+2), (10+5), and (10+1), which are 14, 12, 15, and 11 respectively.

The maximum among those finishing times is 16. This is the earliest possible finish time.

Function Description

Complete the function minTime in the editor below.

minTime has the following parameter(s):

int processorTime[n]: each processorTime[i] denotes the time at which all 4 cores of the ith processor become available

int taskTime[4*n]: each taskTime[i] denotes the execution time of the ith task Returns

int: the earliest time at which all the tasks can be finished

public static int minTime(List<Integer> processorTime, List<Integer> taskTime) {

Collections.sort(processorTime);
Collections.sort(taskTime);
Collections.reverse(taskTime);
int result = 0;
int curTask = 0;
for(int proctime : processorTime){
    for(int i=0; i<4 ; ++i){
        int completionTime = taskTime.get(curTask) + proctime;
        curTask++;
        result = result > completionTime ? result : completionTime;
    }
}
return result;

My initial thought was to group the tasks for each processor in a way so that their sums would be as close to each other as possible. This way, they all finish at around the same time, and this way, it prevents the scenario of a processor finishing all it's tasks super early and then having to wait for another processor to finish all the tasks.

Clearly, that is not what the solution entails. Can someone explain the logic behind the solution?

$\endgroup$
2
  • 1
    $\begingroup$ Please credit the original source for this problem. See cs.stackexchange.com/help/referencing. Can you link to the problem statemetn? $\endgroup$
    – D.W.
    Aug 30 at 9:30
  • $\begingroup$ The contest has ended, and unfortunately there is no option to view the problem statement. $\endgroup$ Aug 30 at 20:23
0
$\begingroup$

Here, the division of processors into cores is not relevant. You simply have to assign $4n$ tasks to $4n$ cores so that the maximum completion time is minimized. Naturally, an optimal algorithm will assign the task with larger execution time to a processor's core with the smaller processor time. In other words, let $(e_1,\dotsc,e_{4n})$ be the decreasing order of the execution time, and $(p_1,\dotsc,p_{4n})$ be the increasing order of the processor time. A task with execution time $e_{i}$ will be assigned to the processor's core with processing time $p_i$.

Proof Hint: For the sake of contradiction, assume that in the optimal solution, $e_{i_1}$ is assigned to $p_{j_1}$, and $e_{i_2}$ is assigned to $p_{j_2}$, such that $e_{i_1} \geq e_{i_2} $, and $p_{j_1} \geq p_{j_2}$. Now swap the processes, i.e., assign $e_{i_1}$ to $p_{j_2}$, and $e_{i_2}$ is assigned to $p_{j_1}$. You can show that the maximum completion time will only decrease. Therefore, it is always good to assign a task with larger execution time to a core with smaller processor time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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