19.4.2. Example Execution of the Algorithm

Try these first

1. 1.

   What is a greedy algorithm?

   Hint

   Think about choosing the best option at every moment.

2. 2.

   Describe the goal of interval scheduling.

   Hint

   Think about fitting as many items into a limited space.

3. 3.

   What does a greedy algorithm aim to achieve?

   • Global optimum
   • Formatted output
   • Data structure sorting

   Hint

   Think about what goal greedy choices lead to.

4. 4.

   True or False: A greedy algorithm always guarantees a globally optimal solution.

   • True
   • False

   Hint

   Reflect on when greedy choices might lead astray.

5. 5.

   Given the intervals [(1, 3), (2, 4), (4, 5), (3, 6), (7, 8)], list the maximum set of non-overlapping intervals.

   Hint

   Sort by finish time first!

6. 6.

   Prove that for a set of n intervals, the greedy algorithm's choice based on finishing times always results in the maximum subset.

   Hint

   Utilize base and inductive case strategy.