Multiple “intervals” are to be given as tasks. Calculate the maximum work time (minutes) to assign to one worker
Implement the method “int Problem2#getMaxWorkingTime(List intervals)”.
- Return the maximum time to work on a task when one worker takes it.
- Time assignment unit shall be based on tasks. (i.e. Task assignment shall be either to complete the whole task, or to do nothing for it.)
- The length of the interval, time required to complete the task, is calculated by subtracting "end time" from "start time". (e.g. If [12:00, 13:00] is given, the length of the task is 60 min.)
- Return 0 if the argument is null or an empty list.
- The argument (a list of “intervals”) must not contain null.
- The number of “intervals” must not exceed 10,000
In Figure 3 , work time is maximized when three tasks [“06:00”, “08:30”], [“09:00”, “11:30”], and [“12:30”, “14:00”], are assigned. Therefore, the answer is 390 (minutes).
Figure 3: An example of input and answer
6 7 8 9 10 11 12 13 14
---------------- --------------- ---------------
------- --------------------------------
-------------------
To me it appears to as a problem whose answer I can find simply by subtracting the Interval with max end-time i.e 14:00 with Interval which has smallest start-time, say 14:00 minus 06:00 answer is 480 minutes (since 6 to 14 has 8 hours in it so 8*60 minutes = 480 minutes) but the correct answer is 390 minutes Can any one please help me explaining how to solve this problem...?
Ok, so you have intervals and want to find their subset, in which the intervals don't intersect and have maximum total length (sum of lengths).
There's an
solution using DP. Consider intervals [xi, yi) sorted by yi and Li the answer if we end with interval i. That interval could be the last one, or there could be some last interval j that was added before it (and doesn't intersect it, so yj ≤ xi, which thanks to the sorting property equates to j ≤ ki for some index ki, which can be found by binsearch). Trying out all of them, we get
where we can set L0 = 0. Making one more array
, we can rewrite it to Li = yi - xi + Mki.
So all you need to do is:
ok so now I have a helping hand so lets get started to solve this problem with the steps you have mentioned Lets write it down the intervals [06:00-08:30], [08:00-09:00], [09:00-11:00], [09:00-11-30], [12:30-14:00], [10:30-14:00] total Intervals = 6
Creating one more array 'M' (length(M) = 6)
step 1) sort the intervals by their ends [06:00-08:30], [08:00-09:00], [09:00-11:00], [09:00-11-30], [12:30-14:00], [10:30-14:00] sorted done !!
step 2)iterate the intervals in increasing order; [06:00-08:30], [08:00-09:00], [09:00-11:00], [09:00-11-30], [12:30-14:00], [10:30-14:00] iteration started i is now set to 0
for interval i (i.e for Interval 0 which is [06:00-08:30]), binary-search ki (i.e k0) but what is k0 ?? Compute Li i.e (L0) which is done by [08:30 minus 06:00] answer is 150 minutes Hence L0 = 150 minutes
Now computing Mi, Mi = max of j<=i * Li Here i = 0, assuming j = 0, max of 0 is 0 itself multiplying with L0 which will make it 0, I m doing wrong i guess ??
can you correct me please ?
Mi = max(L[0]...L[i])
you don't multiply it with the index