19.3.4. Counterexamples to Strategies

Try these first

1. 1.

   Define a greedy algorithm in your own words.

   Hint

   Think about choices made without looking ahead.

2. 2.

   What is interval scheduling in the context of algorithms?

   Hint

   Consider a room booked at different times.

3. 3.

   What is a characteristic of a greedy algorithm?

   • A. It always finds the global optimum.
   • B. It makes local optimal choices.
   • C. It revisits previous decisions.

   Hint

   Consider how greedy algorithms settle for choices.

4. 4.

   True or False: The earliest start time always leads to maximizing bookings in interval scheduling.

   • True
   • False

   Hint

   Reflect on how overlapping bookings affect scheduling.

5. 5.

   You have 5 bookings prioritized by the following intervals: (1, 4), (2, 3), (3, 6), (4, 7), (5, 8). Using the earliest finish time strategy, determine the maximum number of non-overlapping bookings.

   Hint

   Firstly, sort by finish times and find compatible slots.

6. 6.

   Construct a counterexample demonstrating that the strategy of choosing bookings based on the minimum number of conflicts can fail.

   Hint

   Consider a scenario where minimized conflicts lead to total exclusion of useful options.