Activity Selection In the Activity Selection problem, we wish to select a maximum-size subset of mutually compatible act
Posted: Fri May 20, 2022 11:14 am
Activity Selection
In the Activity Selection problem, we wish to select a maximum-size
subset of mutually compatible activities
We know that ordering by the finish times produces an optimal
solution.
1. Show an input for which ordering by the starting times does not
produce an optimal solution.
2. Show an input for which ordering by length (shortest to longest)
does not produce an optimal solution.
3. The degree of an activity is the number of activities whose time
intervals intersect with it. Show an input for which ordering
by degree (smallest to largest) does not produce an optimal
solution.
In the Activity Selection problem, we wish to select a maximum-size
subset of mutually compatible activities
We know that ordering by the finish times produces an optimal
solution.
1. Show an input for which ordering by the starting times does not
produce an optimal solution.
2. Show an input for which ordering by length (shortest to longest)
does not produce an optimal solution.
3. The degree of an activity is the number of activities whose time
intervals intersect with it. Show an input for which ordering
by degree (smallest to largest) does not produce an optimal
solution.