19.6.1. Sorting and Scanning

So, now let us look at a completely different problem, a problem called interval scheduling. So, suppose we have a special video class room, where we can deliver online lectures. Now, different teachers want to book the class room to deliver classes and each instructor has a slot that he would like to deliver this lecture in. So, instructor i has a slot, let us starts at a time s i and finishes it at f i. So, you have a slot which starts at s i and finishes at f i, now two instructors may have overlapping slot. So, our task is to look at the set of bookings and chooses a subset which is feasible that is no two bookings that we choose interfere with each other. So, there we maximize a number of teachers who get to use the room.

Interval scheduling revolves around the idea of efficiently allocating a limited resource—in this case, a classroom—among various users, in this scenario, teachers. Each instructor has a specific time range for which they want to book the classroom. The goal is to book the maximum number of time slots for teachers while ensuring that their bookings do not overlap, meaning only one class can utilize the room at a time. To achieve this, we employ a greedy algorithm.

Think of a busy restaurant that has a limited number of tables for diners. If multiple families want to book tables at overlapping times, the restaurant must choose which bookings it can accommodate to maximize the number of happy diners. This is similar to scheduling classes in a classroom where overlapping bookings cannot occur.

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.

In implementing the greedy approach to interval scheduling, we start with a list of all possible bookings. The algorithm picks one booking based on a predetermined criterion—typically the one that finishes first—to minimize conflict with other bookings. Once a booking is selected, any other meeting that overlaps with this chosen booking is then removed from the list of potential bookings. By continuously selecting bookings this way, we simplify the problem and work towards maximizing the number of non-conflicting bookings.

Imagine a game of Tetris, where you must place blocks of varying shapes onto the board without overlapping them. Each block you place represents a booking while any decision that leads to interference with others must be avoided to ensure a successful game.

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... this greedy strategy is clearly flopped.

While it might seem intuitive to select the booking that starts earliest, this approach does not necessarily yield the optimal solution. Counterexamples can demonstrate situations where prioritizing earlier start times leads to blocking out too many subsequent bookings, therefore minimizing the total number that can be accommodated. Alternatively, selecting the booking that finishes earlier is often a better strategy, as it potentially leaves more room for subsequent bookings.

Picture a school assembly where the schedule has multiple speakers. If the shortest speaker (in terms of speaking duration) were placed first, it might lead to a crowded schedule, preventing longer, more critical speeches from being scheduled down the line. Instead, placing slots where they allow maximum speaker time leads to a smoother assembly with more participants.

So, here is a fourth strategy... if we begin with whose start time is earliest, let us choose the one whose finished time is earliest. So, can we come up with the counter example or should we instead try to prove this is correct.

Choosing the booking that finishes earliest is a proven effective strategy in the interval scheduling problem. By prioritizing the completion time of bookings, we create gaps that allow for new bookings to be scheduled in previously occupied time slots. This method not only follows a logical progression to maximize bookings but also ensures that we continuously allow other potential bookings to fill in time effectively, thus increasing overall room utilization.

Consider planning a series of doctor appointments in a clinic. If the doctor sees patients with shorter check-up times earlier, they are able to accommodate more patients throughout the day. This allows new patients to arrive and receive care without extensive waiting times, optimizing both the doctor’s and patients’ time.

--