dizhu2016
BAN USER- 0of 0 votes
AnswersSuppose there are N number of clusters, B number of machines and number of tasks in clusters are stored in an array named a. The goal is to minimize the single most overloaded machine and every cluster must be given at least one machine. Output should be one integer representing the number of the tasks in the busiest machine (rounded up).
- dizhu2016 in United States
1<=N<=500000
N<=B<=2000000
1<=ai<=5000000
for example, N=2,B=7, a=[200,450], output should be 100.
Any ideas?
Thanks| Report Duplicate | Flag | PURGE
Algorithm
I just figured out a simple way to do this. Let me know what do you think.
The idea is to create a double type array with size equal to the number of clusters, name it as double d[]. d[i] is the number of machine assigned to cluster i. Though d[] should be an integer, we assume it is a double type first and a machine can be taken as a fraction.
d[i] = a[i] * total number of machine / total number of task
. This means we evenly divide all the task to each machine and work out the number of machines required for each clusters by a justifiable way despite machine needs be cutting into fraction. For the example of a[]=[200,450], a d[] should be create as [2.1538461538461537, 4.846153846153846]
Then we are going to make the adjustment. This means we are going to converge the double value of d[i] to the smaller closest integer value. This also equivalently means we are going to increase the number of tasks per machine in each cluster corresponding to the dropping value of d[i]. How much value dropped of d[i] by percentage is equal to how much the number of tasks per machine in each cluster raised by percentage.
Then the outcome should be simple to get. We should choose the cluster k which has d[k] with smallest drop by percentage after converged to nearest smaller integer. The answer is
a[i] / d[k]
.
For this example, we should choose cluster 0, since 2.1538461538461537 to 2 only dropped 6.9% and raise the number of task per machine by 6.9%, whereas for cluster 1, we will raise the number of task per machine by 21% if we change the 4.846153846153846 number of machine to 4.
Hopefully there is no loophole for this idea. To me this seems right and simple.
Ok. Thanks. I found a solution from a forum, which basically follows your idea. I am clear now.
- dizhu2016 July 22, 2017