I've never worked on this problem. Coming up with a solution is one thing, but coming up with the optimal solution is quite another. It seems to resemble the bin packing problem[^], which is NP-complete, but it has the additional constraint of having to assign contiguous jobs.
Checking whether the time limit of T1 can be met is easier than optimizing from scratch. You don't need DP, you don't need sorting, your greedy solution already does the job. It only takes linear time and there is nothing better you could do in that sense: the input all needs to be seen anyway so anything will take at least linear time.
Search for the lowest T1 such that the previous algorithm returns True.
For example, that can be done in O(log(S)) where S is the Sum of all times, doing it in O(S) would not be polynomial time because S can be exponential in the size of the input (imagine if the times are very few but very large integers), but log(S) is fine.
Hmm so you actually direct me to some approach where I have to only divide each time by 2.
The logic behind that, I think, is:
If at first we see that we can split our jobs (Total time = S) such that T1 = S (That is, K equals at least to 1), then let's find out if we can split it to 2 assignees equally - now we'll send to our first algorithm as a parameter: 0.5*S.
So we divide by 2 and send to the first algorithm, so on...
Am I right?
BTW, how do I think about proving the optimality of such an algprithm?
@harold aptroot -
Sorry, but I'm not sure I got your point.
I agree if you mean the following: In case we've divided S by 2, and Algorithm1(T1) == TRUE, then we know for sure that T_Optimal <= T1.
So the algorithm should go as I described before, no? With the division each time by 2. But it's probably not sufficient as we may skip on some T1 which gives FALSE, and from there we don't know the amount of time units to add up...
Genius. It reminds me a little bit the procedure of Partition in QuickSort.
So we sort with Algorithm1(S), if it returns TRUE we call Algorithm(0.5 * S), and so on...
If at some point (after i steps) we call Algorithm1(0.5^i * S), and it returns FALSE, we call Algorithm1(0.5 * (0.5^i * S + 0.5^(i-1) * S)), and so on...
Hmmm actually now I'm not sure about my suggestion.
Should I actually initialize an array of size S with all the natural numbers from 1 to S?
If the range was [25, 50] and 38 was picked as the midpoint and Algorithm1(38) is True, then the next range is [25, 38]. No problems, just updating the endpoint of the range. Taking the average of 25 and 38 ("divide by 2" is only what happens when the startpoint is zero) also does not cause a problem. Taking an average never "escapes" from the range.
For some reason I can't explain I don't see your last comment on this topic, where you mentioned the idea of saving the start-point and end-point. (I see it through the notifications on the site and in my mail)
Amazing, simple and genius.
So we actually suggested a polynomial greedy algorithm.
BTW, how do you approach to prove the correctness, specifically the optimality of this algorithm?
The "sub problem" is to not assign more "job time" than T1 to any one assignee.
Since there was no constraint that said an assignee could not be "idle" (or "optimal"), one can simply read contiguous jobs (in say reverse time order) and assign "blocks" until they're used up or assignees are at capacity.
The "dynamic" part is the looping through the job list and assigning them (depleting the job list while adding to an assignee's jobs.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
I was wondering if anyone knew whether the implementation of the
hash function in a hash map is the same asin a hash table, i.e. are
the same implementation options available for a hash map?
Also, I wonder why Hash tables were deprecated in Java 5 other than
having multiple locks in the ConcurrentHashMap class and whether
ConcurrentHashMap implements the same hash functions as a Hash Table.
This is likely a question for Oracle or Microsoft or for someone who has worked there. If anyone knows, please share.