19.4.2.2. Selection Process

Try these first

1. 1.

   Define the term 'Greedy Algorithm.'

   Hint

   Think about how such decisions can affect the outcome.

2. 2.

   What is the primary goal of interval scheduling?

   Hint

   Consider the implications of overlapping time slots.

3. 3.

   What is a greedy algorithm?

   • A method that guarantees optimal solutions.
   • An approach that makes locally optimal choices.
   • A strategy that avoids all risks.

   Hint

   Remember the nature of decision-making.

4. 4.

   True or False: The finish-time strategy always yields an optimal solution in interval scheduling.

   • True
   • False

   Hint

   Consider the foundational proof discussed in class.

5. 5.

   Given the intervals [(0, 5), (1, 2), (3, 4), (2, 3), (4, 6)], find the maximum number of non-overlapping intervals using the finish-time strategy.

   Hint

   Pay attention to finish times and overlaps.

6. 6.

   Demonstrate the failure of the shortest interval strategy with an example of your own design.

   Hint

   Analyze how overlaps change outcomes.