## Saturday, March 19, 2016

### Balance server capacity | allenlipeng47

Balance server capacity | allenlipeng47
There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?
Ex:
Servers capacity limits: 8, 16, 8, 32
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8
For this example, the program should say 'true'.
Ex2:
Server capacity limits: 1, 3
For this example, program should return false.
Solution:
First impression would be using greedy algorith. Each time, put the max task in the max capacity server. But it won't find the best answer for a lot of times. An counter-example is: Server capacity [4, 3], task[3, 2, 2].
So the solution should be use recursion to traverse the whole result possibilities.
1.     public static int[] balanceServer(int[] server, int[] task){
3.             return null;
4.         }
5.         int[] result = new int[task.length];
6.         for(int i=0;i
7.             result[i] = -1;
8.         }
10.         return result;
11.     }
12.     //put task[n] in the server, and save the result
13.     public static boolean balanceServerUtil(int[] server, int[] task, int n, int[] result){
15.             return true;
16.         }
17.         for(int i=0;i
20.                 result[n] = i;
22.                     return true;
23.                 }
25.                 result[n] = -1;
26.             }
27.         }
28.         return false;
29.     }
# Check if there are already 8 tasks scheduled to the given server
if len(capacity_needs) == 0:
return True
for i in range(len(capacity_needs)):
need = capacity_needs[i]
new_needs = copy(capacity_needs)
del new_needs[i]
for j, limit in enumerate(capacity_limits):
if len(assignments[i]) < 8 and sum(assignments[j]) + need <= limit:
new_assignments = copy(assignments)
new_assignments[j].append(need)
return True
print need
print assignments
return False