You are given N movie screenings with start times s i and end times e i.
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
You are given $N$ movie screenings with start times $s_i$ and end times $e_i$. You want to maximize the total number of non-overlapping movies you can watch. Which greedy strategy yields an optimal schedule?
Show answer & explanation
The Earliest Deadline First (EDF) / Earliest Ending Time greedy strategy is proven optimal for the activity selection problem. By selecting movies that finish earliest, you leave the maximum amount of time for subsequent movies, maximizing the count of non-overlapping selections. Options B (earliest start) and C (shortest duration) can lead to suboptimal solutions by blocking later available activities. Option D (fewest conflicts) is heuristic-based and not guaranteed to be optimal.
Step-by-step Derivation:
Proof sketch: Suppose an optimal solution O does not use the earliest-ending movie m₁ that our greedy algorithm selects. Since m₁ has the earliest end time, we can replace the first movie in O with m₁ without creating conflicts (m₁ ends before or at the same time as O's first movie ends). By induction, the greedy choice at each step leads to an optimal solution. Counter-example for B: movies [(1,3), (2,5), (4,6)] — earliest start picks (1,3), then (4,6) = 2 movies. Earliest end picks (1,3), then (4,6) = 2 movies, but consider [(1,2), (2,3), (3,4)] — earliest start picks (1,2), then (3,4) = 2 movies; earliest end also picks 2. However, for [(1,10), (2,3), (4,5), (6,7)] earliest start picks (1,10) = 1 movie; earliest end picks (2,3), (4,5), (6,7) = 3 movies.