Given n activities with start time (Si) and end time (Fi) and 2 resources.
Pick the activities such that maximum number of activities are finished.
My ideas
I tried to solve it with DP but couldn't figure out anything with DP.So trying with greedy
Approach: Fill resource-1 first greedily and then resource-2 next greedily(Least end time first). But this will not work for this case T1(1,4) T2(5,10) T3(6,12) T4(11,15)
Approach 2:Select tasks greedily and assign it in round robin fashion. This will also not work.
Can anyone please help me in figuring out this?
No need to use DP at all, a Greedy solution suffices, though it is slightly more complicated than the 1-resource problem.
Here, we first sort the intervals by the ending time, earlier first. Then, put two "sentinel" intervals in the resources, both with ending time -∞. Then, keeping grabbing the interval x with lowest x.end, and follow these rules:
The greedy strategy in rule 2 is the key point here: we want to replace the latest ending used resource, since that maximizes the "space" that we have in the other resource to accommodate some future interval with an early start time, making it strictly more likely that future interval will be able to fit.
Let's look the example in the question, with intervals (1,4), (5,10), (6,12), and (11,18) already in sorted order. We begin with both resources having (-∞,-∞) as "sentinel" intervals. Now take the first interval (1,4), and see that it fits, so now we have resource 1 having (1,4) and resource 2 having (-∞,-∞). Next, take (5,10), which can fit in both resources, so we choose resource 1, because it ends the latest, and now resource 1 has (5,10). Next, we take (6,12), which only fits in resource 2, so resource 2 has (6,12). Finally, take (11,18), which fits in resource 1.
Hence, we have been able to fit all four intervals using our Greedy strategy.