19.6.1. Sorting and Scanning

Try these first

1. 1.

   What is a greedy algorithm?

   Hint

   Think about local vs global decisions.

2. 2.

   Why is it important to sort the bookings by finish time?

   Hint

   Consider how we check for overlaps.

3. 3.

   What is the fundamental principle of greedy algorithms?

   • Choose the earliest start time
   • Make local optimal choices
   • Select the longest interval

   Hint

   Think about the nature of greedy decision making.

4. 4.

   True or False: Greedy strategies always produce optimal solutions.

   • True
   • False

   Hint

   Recall the counterexamples discussed in class.

5. 5.

   Assume you have the following time slots: [1, 4], [3, 5], [2, 6], [5, 7]. Find the maximum number of non-overlapping intervals using a greedy approach and explain your reasoning.

   Hint

   Sort by finish time and choose accordingly.

6. 6.

   Given a larger set of bookings, design and describe a more efficient timeline visualization for the above problem to help quickly identify non-overlapping slots.

   Hint

   Think about graphical representations for clarity.