This looks pretty good. Need to spend a little more time reviewing it, but in the meantime could you fix the weird comma placement in the "array =" lists in the test cases?

@mikeb
Thanks for your comment. I've updated my code.

I think maybe it's better to profile different algorithms first. The list sort can sort through a list in O(log(n)) in the best case, and in O(n*log(n)) in the worst case. And it's obvious that the median function is not cheap operation even the array has been sorted.

@xning,

Actually, the complexity of list.sort() is always O(n*log(n)). The old implementation iterates every bin in bins and sorts the available capacity list for each bin. If we have m bins, that'll be O(m*n*log(n)). After that, checkRelAvail() will get the median from a sorted list in O(1) time.

In my implementation, I don't fill the avail map until the bin that we will use is not present. In other word, avail will be used as a cache map. Furthermore, The median will only be calculated when we call checkRelAvail(). The new median() function will take an average of O(n) time, where n is the number of hosts having that bin. The disadvantage of this approach is if a builder fails to take a task and tries to take another task in the same bin, it will calculate the median for that bin again.
Actually, we can even drop the variable avail but cache the median for each bin instead. In this case, the disadvantage will be eliminated. But we have to change the definition of checkRelAvail(). That's why I didn't do it.

@xning,
Actually, the complexity of list.sort() is always O(nlog(n)). The old implementation iterates every bin in bins and sorts the available capacity list for each bin. If we have m bins, that'll be O(mn*log(n)). After that, checkRelAvail() will get the median from a sorted list in O(1) time.
In my implementation, I don't fill the avail map until the bin that we will use is not present. In other word, avail will be used as a cache map. Furthermore, The median will only be calculated when we call checkRelAvail(). The new median() function will take an average of O(n) time, where n is the number of hosts having that bin. The disadvantage of this approach is if a builder fails to take a task and tries to take another task in the same bin, it will calculate the median for that bin again.
Actually, we can even drop the variable avail but cache the median for each bin instead. In this case, the disadvantage will be eliminated. But we have to change the definition of checkRelAvail(). That's why I didn't do it.

Profiling data, please.

How about doing this calculation in host.getLoadData()?

Sorry for my late update. I'm too busy these days.
I will resubmit a new patch in several days and provide more optimized code.

Still planning on submitting a new patch?

@mikem, I did some researches on this problem with @xning. It seems to me that the performance improvement is not obvious because we don't have so many builders.
Considering to the complexity introduced in this patch, I would prefer not to merge it.

ok, thanks. I'll close this out then.