19.3.4. Counterexamples to Strategies

So, broadly if we follow a greedy approach, this is what we would do. Among all the bookings that are not yet allocated and which are still available to allocate. We will pick one based on some local strategy, then we would remove all conflicting bookings, bookings that overlapped with this booking that with the slot that we just allocated and somehow we have to argue that this sequence of bookings that we are choosing maximizes the number of teachers who get to use the room.

In this section, the greedy approach is introduced. The greedy strategy involves selecting one booking from all available options using a local criterion, i.e., making a choice based on the best immediate benefit, and then removing any conflicting bookings from future consideration. The challenge is to demonstrate that this process leads to the best possible outcome—maximizing the number of teachers that can use the room without conflicts.

Imagine a hospital scheduling surgeries. Every time a surgeon wants to book the operating room, the scheduler decides to accept one surgery based on its timing. If they accept a longer surgery, they might have less room for shorter surgeries later in the day. Thus, it’s crucial to choose the surgery time that allows the maximum number of patients to be treated.

So, let us look at some typical greedy strategies that one might wanted. So, one strategy might be to choose the booking whose start time is earliest, but it is not difficult to come up with the counter example.

One potential strategy is to select the booking that begins earliest. However, this is not guaranteed to yield the optimal solution. For instance, if the first booking is a long one, it may block out other shorter bookings that could allow more teachers to use the room. Therefore, this greedy method can lead to suboptimal results, demonstrating the need to evaluate different strategies.

Think of it like a restaurant reservation system: if a diner books a two-hour table for dinner at 5 PM, that time slot cannot accommodate other diners who might want to come in for just an hour at 6 PM and 7 PM. By focusing solely on the earliest booking, the restaurant could potentially miss out on serving several other customers.

And other greedy strategy we might think of is to choose a booking whose interval is shortest. Once again here is a counter example.

Another plausible greedy approach is to select the booking with the shortest duration. However, this too doesn’t guarantee optimal results. Picking a short interval may conflict with longer intervals that could host multiple teachers. Thus, the strategy of selecting based solely on the shortest duration isn't effective as it can lead to losing out on more viable options.

Consider a school that allows classes to be scheduled for different lengths. If the principal always chooses the shortest class first, they might overlook arranging for multiple longer classes which could serve more students, akin to a music school that lets one student book a short lesson while neglecting several other opportunities.

So, the previous example suggest that there is something to do conflicts, so maybe we might choose bookings in terms of how many other bookings they ruled up.

This chunk discusses a strategy whereby a booking is selected based on the least number of overlapping bookings. The rationale is to limit conflicts to ensure that more total bookings can occur. However, this approach also fails to yield maximum results. Choosing a booking just because it excludes fewer options might overlook better opportunities that allow more bookings overall.

Picture a conference trying to schedule talks; if they choose presenters based on the fewest overlaps, they might miss out on combining several talks into one session that could showcase multiple speakers to the audience, similar to picking the least conflicting schedules rather than the most impactful combinations.

So here is a fourth strategy, instead of choosing the one like we begin with whose start time is earliest, let us choose the one whose finished time is earliest.

This strategy involves selecting the booking that finishes earliest rather than starting earliest. Unlike the previous strategies discussed, this approach tends to yield more optimal scheduling. By focusing on the finishing times, it effectively frees up more room for subsequent bookings, allowing more teachers to utilize the space. In this case, we'll aim to prove its effectiveness.

Imagine a conference that fills time slots not by when talks start, but by when they end. This ensures that as soon as one speaker finishes, the next begins, maximizing the number of topics discussed instead of wasting time with lengthy overlaps, keeping audience engagement at its peak.

--