greedy Flashcards
What is the “greedy choice” in the context of the activity-selection problem?
The “greedy choice” in the activity-selection problem is to select the activity with the earliest finish time from the set of given activities. This approach is based on the intuition that by selecting the activity that finishes earliest, we leave more time available for other activities, thus increasing the chance of creating the maximum set of compatible activities.
What is the theorem supporting the greedy choice in the activity-selection problem?
The theorem states that if Sij is a non-empty set of activities between indexes i and j, and am is the activity with the earliest finish time, then: am
is part of some maximum-size subset of mutually compatible activities in Sij
Choosing am leaves Smj as the only non-empty subproblem, thus reducing the number of subproblems to consider.
