raghavsagar92
BAN USERBasically, one way is to solve using recursive backtracking with no memoization.
Given a list of jobs L1 with service times S_i, and a list of servers L2 with with capacities C_i, we try each job on all servers one by one until the list L1 is traversed. Its like Depth First Search with backtracking (in case we don't find the solution along the path).
An improvization would/could be memoization instead of backtracking.
Say, we order the list L1 in descending order of service rates.
The state I would memoize is.
S[Sorted List of remaining capacities in L2, i] => The current state of List L2 after processing the 1st i elements of L1
S[Sorted List of remaining capacities in L2, i] = {-1, 0, 1}
-1 means not yet memoized
0 means not possible
1 means possible
------------------------------------------------------------------------------------------------
The important part is that i am storing List L2 after sorting it, because all servers are identical. (so that we don't have to recompute for the same list in different order)
The idea is compare the median of both arrays:
Let Array A have smaller median M_A than Array B having M_B
M_A <= M_B
1. Delete elements in A before M_A (less than N elements will come before M_A in merged sorted array)
2. Delete elements in B before M_B (less than N elements will come after M_B in merged sorted array)
(be careful to delete equal number of elements from both A and B so that median remains same, and number of elements deleted should be < N/2 in both arrays)
Code:
--------------------------------------------------------------------------------
}
- raghavsagar92 August 05, 2014