See photo 1 for question
photo 2 for tutorial
The Attempt at a Solution
I have 2 questions
1. It seems the 2 methods in part(a) are not optimal.
But I don't know if my counter examples are correct.
If we use the (1) algorithm, that in my drawing 1, it choose event A only. However, choosing B, C and D is better.
If we use (2), that my second drawing shows it will choose either C or B. However, choosing A and D is better.
2. In part b, how to calculate the time needed?
For me, I decompose the greedy algorithm in to 4 steps.(See the tutorial sheet to see which 4 steps)
I know that step 1 takes n times because it compare n events.
step 2 doesn't take time because it choose the event only.
step 3 takes n times again since it compares n events to see which one has time crash and then discard them.
I think step 4 is the tricky. It repeat step 3 with fewer events. I assume i events have been discarded, but I am sure if I can do this.