Greedy Algorithms. You\'re in charge of the Boeing 737NG flight simulator in Sin
ID: 3765945 • Letter: G
Question
Greedy Algorithms. You're in charge of the Boeing 737NG flight simulator in Singapore. This Friday pilots from several major airlines are in town and are available for simulator training. However, only one pilot can be 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 = (P_1, P_2, ,P_n} of n pilots who have training windows with start and finish times (s_i, f_i), 1 select a set S of non-overlapping simulator training sessions that maximizes the number of pilots that can be trained.Explanation / Answer
This is one of the classic problem which can be solved using greedy algorithm. The best solution would be to pickup pilots in increasing order of their finish time for the job.
We can prove this by induction.
Consider any solution S for this pilot problem with at least k jobs where k < n . We claim by induction on k that the greedy
algorithm schedules at least k jobs for the pilot training and that the first k jobs in the greedy schedule finish no later
than the first k jobs in the chosen solution. As per the solution we have discussed.
This immediately implies the result because it shows
that the greedy algorithm schedules at least as many jobs as the optimal solution.
We now prove the claim. The base case, k = 0 is trivial. For the inductive step, consider the
(k + 1)th job i.e the schedule the training for the (k+1)th pilot, say J, in the solution S. Then this training for the pilot(job) begins after the kth job in S ends, which
happens after the kth job in the greedy schedule ends (by the induction hypothesis). Therefore, it
is possible to augment the greedy schedule with the job J without introducing any conflicts. The
greedy algorithm finds a pilot to augment its solution and in particular, picks one that finishes
no later than the time at which J ends. This completes the proof of the claim.
Hence shows that S is the required set.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.