sir how did you know that we should the maximum load that is getting transferred between two parts of an array is the answer?? and why the answer should be the maximum load between two parts of array?
Load balncer (greedy)
Hello @mzk1994
check this and let me know if still it is not clear
base case : if number of jobs of all processors is not divisible by n print -1.
else
find average.
lets say a[i] is the list of jobs assigned to i th processor.
-
from each job a[i] do a[i] - avg. if a[i] is +ve it means it has to export this many jobs to neighbors and -ve means it has to import this may jobs from neighbors .
-
for all i do a[i] =a[i] + a[i - 1] i.e. find sum till i.
-
find max absolute value from a[i] and print it.
explanation:
lets say a[i] after performing step 1 is: [ 2 ,-5, 7, -4]
after performing step 2 array will become [2, -3, 4, 0]
what it means is that first processor has 2 extra jobs and it can export it in 2 round.
2nd processor has 5 jobs to import. It can take 2 from 1st processor, it has still 3 more to import. and it can be done in 3 rounds.
3rd processor has 7 jobs to export. It can export 3 to previous processor in 3 round and it has remaining 4 jobs, which can be exported in 4 rounds to the next processor.
4th processor has to import 4 jobs and it can import it from previous processor in 4 rounds. Hence max rounds is the max absolute value from a[i].