19.3.5. Optimal Strategy and Algorithm

Try these first

1. 1.

   What is a greedy algorithm?

   Hint

   Think about making immediate ‘best’ picks.

2. 2.

   What does interval scheduling involve?

   Hint

   Consider how events can be scheduled in a limited timeframe.

3. 3.

   What is the main goal of the greedy algorithm in interval scheduling?

   • Maximize classroom size
   • Maximize the number of non-overlapping intervals
   • Minimize instructor time

   Hint

   Focus on what we’re trying to achieve with scheduling.

4. 4.

   True or False: A greedy strategy can be proven optimal.

   • True
   • False

   Hint

   Recall how we discussed proof techniques.

5. 5.

   Critically analyze a recently developed scheduling algorithm and compare it against the greedy approach discussed here.

   Hint

   Look for differing outcomes when applying various strategies.

6. 6.

   Design a small Python program that demonstrates the greedy algorithm for interval scheduling, including error handling for overlapping time slots.

   Hint

   Use collections to handle setting and managing booked time intervals effectively.