19.6. Complexity Analysis

Try these first

1. 1.

   What is a greedy algorithm?

   Hint

   Think about what it means to take the best option right now.

2. 2.

   In the interval scheduling problem, what is the goal?

   Hint

   Consider the constraints set by overlapping time slots.

3. 3.

   What is a characteristic of greedy algorithms?

   • They always yield the best solution.
   • They make the best choice in a moment.
   • They require backtracking.

   Hint

   Think about the nature of decisions made at each stage.

4. 4.

   True or False: Choosing the booking with the earliest start time is always optimal.

   • True
   • False

   Hint

   Reflect on how overlaps can affect choices.

5. 5.

   Create a new algorithm for interval scheduling that selects bookings not only by finish time but also considers potential overlaps in a different way.

   Hint

   Look into grouping similar bookings based on their time ranges.

6. 6.

   Prove that your algorithm produces an optimal solution by comparing it with another known successful greedy algorithm.

   Hint

   Case studies can help corroborate how different paths lead to the same positive end.