Questions: Activity Selection Problem Using Greedy Algorithms

Question 1

You need to schedule the maximum number of non-overlapping activities. Which sorting criterion guarantees an optimal greedy solution?

• A. Sort by start time — activities starting earliest should be prioritized
• B. Sort by end time — finishing earliest leaves the most remaining capacity for future activities
• C. Sort by duration — shortest activities maximize the number that fit
• D. Sort by number of conflicts — activities with fewer conflicts should be selected first

Answer: (B)

Sorting by end time is the only criterion that provably guarantees optimality. Sorting by start time fails because an activity starting early might run very long and block many others. Sorting by duration fails because a short activity might sit in the middle of the timeline, blocking two longer ones that together could have fit. Earliest-finish-time is correct because it leaves maximum remaining time after each selection, which is exactly what the greedy-choice property formalizes.

Question 2

The greedy-choice property for activity selection states that...

• A. The activity with the fewest overlapping activities is always in some optimal solution
• B. The earliest-starting activity is always in some optimal solution
• C. The earliest-finishing activity is always in some optimal solution
• D. Any activity can be the first selection without affecting the number selected

Answer: (C)

The greedy-choice property says the earliest-finishing activity a₁ is always in some optimal solution. The proof is an exchange argument: if an optimal solution uses some other activity a' instead of a₁, you can swap a' for a₁ without creating new conflicts (since a₁ finishes no later than a'), producing a valid solution of the same size. This swap argument is what makes the greedy approach provably correct — not just heuristically sensible. Option B (earliest start) is a common trap; it is not provably optimal.

Question 3

Sorting activities by shortest duration usually maximizes the number of non-overlapping activities selected.

• T. True
• F. False

Answer: False

This is a common misconception. A short activity positioned in the middle of the timeline can block two longer activities that together would have increased the total count. For example, given activities A(1–8), B(3–4), C(5–9), sorting by duration selects B(duration 1) first, then nothing else fits around it. Sorting by end time selects B(ends 4), then C(ends 9), giving 2 activities. Only end-time ordering is provably optimal.

Question 4

The activity selection problem can be solved optimally in O(n log n) time, with the sort dominating and the selection pass requiring only O(n).

• T. True
• F. False

Answer: True

After sorting by end time in O(n log n), the greedy selection is a single linear scan: iterate through activities, and select each one whose start time is at or after the finish time of the last selected activity. This O(n) pass requires no backtracking or reconsideration of earlier choices, which is what makes the greedy approach efficient. Dynamic programming for the weighted variant is O(n²) or O(n log n) with binary search — more expensive because it cannot rely on the greedy-choice property.

Question 5

Explain why sorting activities by end time — rather than by start time or shortest duration — leads to an optimal greedy solution.

Model answer: Sorting by end time works because finishing earliest leaves the maximum amount of remaining timeline available for subsequent activities. Any other selection could block more future choices. The greedy-choice property formalizes this: the earliest-finishing activity is always in some optimal solution (provable by an exchange argument — swapping any other first choice for the earliest-finishing activity never reduces the total count). Start time fails because an early-starting activity may run too long; duration fails because a short activity in the middle can block two longer compatible activities.

The core insight is that the greedy algorithm's correctness is not intuitive — it requires the exchange argument to prove. Understanding this proof is what distinguishes genuine mastery from pattern-matching: it shows *why* end time is special (it minimizes the 'cost' of each selection in terms of future capacity consumed) and why no other simple criterion achieves the same guarantee.