# Schedule jobs so that each server gets equal load

There are n servers. Each server i is currently processing a(i) amount of requests. There is another array b in which b(i) represents the number of incoming requests that are scheduled to server i. Reschedule the incoming requests in such a way that each server i holds an equal amount of requests after rescheduling. An incoming request to server i can be rescheduled only to server i-1, i, i+1. If there is no such rescheduling possible then output -1 else print number of requests hold by each server after rescheduling.

Examples:

```Input : a = {6, 14, 21, 1}
b = {15, 7, 10, 10}
Output : 21
b(0) scheduled to a(0) --> a(0) = 21
b(1) scheduled to a(1) --> a(1) = 21
b(2) scheduled to a(3) --> a(3) = 11
b(3) scheduled to a(3) --> a(3) = 21
a(2) remains unchanged --> a(2) = 21

Input : a = {1, 2, 3}
b = {1, 100, 3}
Output : -1
No rescheduling will result in equal requests.
```

Approach: Observe that each element of array b is always added to any one element of array a exactly once. Thus the sum of all elements of array b + sum of all elements of old array a = sum of all elements of new array a. Let this sum be S. Also all the elements of new array a are equal. Let each new element is x. If array a has n elements, this gives

``` x * n = S
=> x = S/n     ....(1)
```

Thus all the equal elements of new array a is given by eqn(1). Now to make each a(i) equals to x we need to add x-a(i) to each element. We will iterate over entire array a and check whether a(i) can be made equal to x. There are multiple possibilities:
1. a(i) > x: In this case a(i) can never be made equal to x. So output -1.
2. a(i) + b(i) + b(i+1) = x. Simply add b(i) + b(i+1) to a(i) and update b(i), b(i+1) to zero.
3. a(i) + b(i) = x. Add b(i) to a(i) and update b(i) to zero.
4. a(i) + b(i+1) = x. Add b(i+1) to a(i) and update b(i+1) to zero.

After array a is completely traversed, check whether all elements of array b are zero or not. If yes then print a(0) otherwise print -1.

Why b(i) is updated to zero after addition?
Consider a test case in which b(i) is neither added to a(i-1) nor a(i). In that case, we are bounded to add b(i) to a(i+1). Thus while iterating over the array a when we begin performing computations on element a(i), first we add element b(i-1) to a(i) to take into consideration above possibility. Now if b(i-1) is already added to a(i-1) or a(i-2) then, in that case, it cannot be added to a(i). So to avoid this double addition of b(i) it is updated to zero.

The stepwise algorithm is:

```1. Compute sum S and find x = S / n
2. Iterate over array a
3. for each element a(i) do:
a(i) += b(i-1)
b(i-1) = 0;
if a(i) > x:
break
else:
check for other three possibilities
and update a(i) and b(i).
4. Check whether all elements of b(i) are
zero or not.
```

Implementation:

## C++

 `// CPP program to schedule jobs so that ` `// each server gets equal load. ` `#include ` `using` `namespace` `std; ` ` `  `// Function to find new array a ` `int` `solve(``int` `a[], ``int` `b[], ``int` `n) ` `{ ` `    ``int` `i; ` `    ``long` `long` `int` `s = 0; ` ` `  `    ``// find sum S of both arrays a and b. ` `    ``for` `(i = 0; i < n; i++)  ` `        ``s += (a[i] + b[i]);     ` ` `  `    ``// Single element case. ` `    ``if` `(n == 1) ` `        ``return` `a + b; ` ` `  `    ``// This checks whether sum s can be divided ` `    ``// equally between all array elements. i.e. ` `    ``// whether all elements can take equal value ` `    ``// or not. ` `    ``if` `(s % n != 0) ` `        ``return` `-1; ` ` `  `    ``// Compute possible value of new array  ` `    ``// elements. ` `    ``int` `x = s / n; ` ` `  `    ``for` `(i = 0; i < n; i++) { ` ` `  `        ``// Possibility 1 ` `        ``if` `(a[i] > x)  ` `            ``return` `-1;       ` ` `  `        ``// ensuring that all elements of  ` `        ``// array b are used. ` `        ``if` `(i > 0) { ` `            ``a[i] += b[i - 1]; ` `            ``b[i - 1] = 0; ` `        ``} ` ` `  `        ``// If a(i) already updated to x  ` `        ``// move to next element in array a. ` `        ``if` `(a[i] == x) ` `            ``continue``; ` ` `  `        ``// Possibility 2 ` `        ``int` `y = a[i] + b[i]; ` `        ``if` `(i + 1 < n) ` `            ``y += b[i + 1]; ` `        ``if` `(y == x) { ` `            ``a[i] = y; ` `            ``b[i] = b[i + 1] = 0; ` `            ``continue``; ` `        ``} ` ` `  `        ``// Possibility 3 ` `        ``if` `(a[i] + b[i] == x) { ` `            ``a[i] += b[i]; ` `            ``b[i] = 0; ` `            ``continue``; ` `        ``} ` ` `  `        ``// Possibility 4 ` `        ``if` `(i + 1 < n &&  ` `            ``a[i] + b[i + 1] == x) { ` `            ``a[i] += b[i + 1]; ` `            ``b[i + 1] = 0; ` `            ``continue``; ` `        ``} ` ` `  `        ``// If a(i) can not be made equal  ` `        ``// to x even after adding all  ` `        ``// possible elements from b(i)  ` `        ``// then print -1. ` `        ``return` `-1; ` `    ``} ` ` `  `    ``// check whether all elements of b  ` `    ``// are used. ` `    ``for` `(i = 0; i < n; i++)  ` `        ``if` `(b[i] != 0) ` `            ``return` `-1;     ` ` `  `    ``// Return the new array element value. ` `    ``return` `x; ` `} ` ` `  `int` `main() ` `{ ` `    ``int` `a[] = { 6, 14, 21, 1 }; ` `    ``int` `b[] = { 15, 7, 10, 10 }; ` `    ``int` `n = ``sizeof``(a) / ``sizeof``(a); ` `    ``cout << solve(a, b, n); ` `    ``return` `0; ` `} `

## Java

 `// Java program to schedule jobs so that ` `// each server gets equal load. ` `class` `GFG  ` `{ ` ` `  `// Function to find new array a ` `static` `int` `solve(``int` `a[], ``int` `b[], ``int` `n) ` `{ ` `    ``int` `i; ` `    ``int` `s = ``0``; ` ` `  `    ``// find sum S of both arrays a and b. ` `    ``for` `(i = ``0``; i < n; i++)  ` `        ``s += (a[i] + b[i]);  ` ` `  `    ``// Single element case. ` `    ``if` `(n == ``1``) ` `        ``return` `a[``0``] + b[``0``]; ` ` `  `    ``// This checks whether sum s can be divided ` `    ``// equally between all array elements. i.e. ` `    ``// whether all elements can take equal value ` `    ``// or not. ` `    ``if` `(s % n != ``0``) ` `        ``return` `-``1``; ` ` `  `    ``// Compute possible value of new array  ` `    ``// elements. ` `    ``int` `x = s / n; ` ` `  `    ``for` `(i = ``0``; i < n; i++)  ` `    ``{ ` ` `  `        ``// Possibility 1 ` `        ``if` `(a[i] > x)  ` `            ``return` `-``1``;    ` ` `  `        ``// ensuring that all elements of  ` `        ``// array b are used. ` `        ``if` `(i > ``0``)  ` `        ``{ ` `            ``a[i] += b[i - ``1``]; ` `            ``b[i - ``1``] = ``0``; ` `        ``} ` ` `  `        ``// If a(i) already updated to x  ` `        ``// move to next element in array a. ` `        ``if` `(a[i] == x) ` `            ``continue``; ` ` `  `        ``// Possibility 2 ` `        ``int` `y = a[i] + b[i]; ` `        ``if` `(i + ``1` `< n) ` `            ``y += b[i + ``1``]; ` `        ``if` `(y == x)  ` `        ``{ ` `            ``a[i] = y; ` `            ``b[i]= ``0``; ` `            ``continue``; ` `        ``} ` ` `  `        ``// Possibility 3 ` `        ``if` `(a[i] + b[i] == x)  ` `        ``{ ` `            ``a[i] += b[i]; ` `            ``b[i] = ``0``; ` `            ``continue``; ` `        ``} ` ` `  `        ``// Possibility 4 ` `        ``if` `(i + ``1` `< n &&  ` `            ``a[i] + b[i + ``1``] == x)  ` `        ``{ ` `            ``a[i] += b[i + ``1``]; ` `            ``b[i + ``1``] = ``0``; ` `            ``continue``; ` `        ``} ` ` `  `        ``// If a(i) can not be made equal  ` `        ``// to x even after adding all  ` `        ``// possible elements from b(i)  ` `        ``// then print -1. ` `        ``return` `-``1``; ` `    ``} ` ` `  `    ``// check whether all elements of b  ` `    ``// are used. ` `    ``for` `(i = ``0``; i < n; i++)  ` `        ``if` `(b[i] != ``0``) ` `            ``return` `-``1``;  ` ` `  `    ``// Return the new array element value. ` `    ``return` `x; ` `} ` ` `  `// Driver code ` `public` `static` `void` `main(String[] args)  ` `{ ` `    ``int` `a[] = { ``6``, ``14``, ``21``, ``1` `}; ` `    ``int` `b[] = { ``15``, ``7``, ``10``, ``10` `}; ` `    ``int` `n = a.length; ` `    ``System.out.println(solve(a, b, n)); ` `} ` `}  ` ` `  `// This code contributed by Rajput-Ji `

## Python3

 `# Python3 program to schedule jobs so that  ` `# each server gets an equal load.  ` ` `  `# Function to find new array a  ` `def` `solve(a, b, n):  ` ` `  `    ``s ``=` `0` ` `  `    ``# find sum S of both arrays a and b.  ` `    ``for` `i ``in` `range``(``0``, n):  ` `        ``s ``+``=` `a[i] ``+` `b[i]      ` ` `  `    ``# Single element case.  ` `    ``if` `n ``=``=` `1``:  ` `        ``return` `a[``0``] ``+` `b[``0``]  ` ` `  `    ``# This checks whether sum s can be divided  ` `    ``# equally between all array elements. i.e.  ` `    ``# whether all elements can take equal value  ` `    ``# or not.  ` `    ``if` `s ``%` `n !``=` `0``:  ` `        ``return` `-``1` ` `  `    ``# Compute possible value of new  ` `    ``# array elements.  ` `    ``x ``=` `s ``/``/` `n  ` ` `  `    ``for` `i ``in` `range``(``0``, n):  ` ` `  `        ``# Possibility 1  ` `        ``if` `a[i] > x:  ` `            ``return` `-``1`     ` `  `        ``# ensuring that all elements of  ` `        ``# array b are used.  ` `        ``if` `i > ``0``:  ` `            ``a[i] ``+``=` `b[i ``-` `1``]  ` `            ``b[i ``-` `1``] ``=` `0` `         `  `        ``# If a(i) already updated to x  ` `        ``# move to next element in array a.  ` `        ``if` `a[i] ``=``=` `x:  ` `            ``continue` ` `  `        ``# Possibility 2  ` `        ``y ``=` `a[i] ``+` `b[i]  ` `        ``if` `i ``+` `1` `< n:  ` `            ``y ``+``=` `b[i ``+` `1``]  ` `         `  `        ``if` `y ``=``=` `x:  ` `            ``a[i] ``=` `y  ` `            ``b[i] ``=` `0` `            ``if` `i ``+` `1` `< n: b[i ``+` `1``] ``=` `0` `            ``continue` `         `  `        ``# Possibility 3  ` `        ``if` `a[i] ``+` `b[i] ``=``=` `x:  ` `            ``a[i] ``+``=` `b[i]  ` `            ``b[i] ``=` `0` `            ``continue` `         `  `        ``# Possibility 4  ` `        ``if` `i ``+` `1` `< n ``and` `a[i] ``+` `b[i ``+` `1``] ``=``=` `x:  ` `            ``a[i] ``+``=` `b[i ``+` `1``]  ` `            ``b[i ``+` `1``] ``=` `0` `            ``continue` `         `  `        ``# If a(i) can not be made equal  ` `        ``# to x even after adding all  ` `        ``# possible elements from b(i)  ` `        ``# then print -1.  ` `        ``return` `-``1` `     `  `    ``# check whether all elements of b  ` `    ``# are used.  ` `    ``for` `i ``in` `range``(``0``, n):  ` `        ``if` `b[i] !``=` `0``: ` `            ``return` `-``1`     ` `  `    ``# Return the new array element value.  ` `    ``return` `x  ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"``:  ` ` `  `    ``a ``=` `[``6``, ``14``, ``21``, ``1``]  ` `    ``b ``=` `[``15``, ``7``, ``10``, ``10``]  ` `    ``n ``=` `len``(a)  ` `    ``print``(solve(a, b, n)) ` `     `  `# This code is contributed by Rituraj Jain `

Output:

```21
```

Time Complexity: O(n)
Auxiliary Space : O(1) If we are not allowed to modify original arrays, then O(n)

## tags:

Arrays Greedy Arrays Greedy