HINT: This is similar to the activity scheduling problem (20 points) Greedy Algo
ID: 3766581 • Letter: H
Question
HINT: This is similar to the activity scheduling problem
(20 points) Greedy Algorithms. You're in charge of t simulator in Singapore. This Friday pilots from several mejor town and are available for simulator training However, on- on in the simulator at one time, and each pilot must can only receive the training during a specific window of time. Given a set P (Pi, P,, P) of n pilots who have training windows with start and finish times (s, f). 1sis n, select a set S of non-overlapping simulator training sessions that maximizes the number of pilots that can be trained.Explanation / Answer
Let I be the set of intervals (si,fi) 1<=i<=n .
Greedy Algorithm:
Let S be the solution set.
Initialize it to empty.
1) sort I according to the right most end and let the Sorted I be Is.
2) add the first interval of Is to S.
3) Iterate throgh Is starting from the second interval and c be the current interval of iteration in Is.
4) If the left end of c is greater than right end of last interval that was added to S then we add c to S.
5) If the left end of c is not greater than right end of last interval that was added to S then we just move to the next interval of Is.
Finally S is the solution to the given problem.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.