19.3. Interval Scheduling Problem

So, now let us look at a completely different problem, a problem called interval scheduling. So, suppose we have a special video classroom, where we can deliver online lectures. Now, different teachers want to book the classroom 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 start 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 slots.

Interval scheduling is about efficiently utilizing a resource—in this case, a lecture room. Each teacher has a specific time range (from start time s_i to finish time f_i) when they want to use the room. The challenge arises when these time slots overlap, making it impossible for two teachers to use the room simultaneously. Therefore, we need to find a way to choose a set of non-overlapping time slots that maximizes usage for the teachers.

Imagine a single conference room in an office where multiple meetings are scheduled. Each meeting has a starting and finishing time. If two meetings overlap, only one can take place in that room. The interval scheduling problem aims to find a way to schedule as many meetings as possible in the conference room without conflicts.

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 we just allocated...

The greedy approach for scheduling requires selecting a booking based on a specific, locally optimal criterion. After a booking is selected, any overlapping bookings are removed from the list of potential options. This greedy choice is based on the idea that making a local optimum choice at each step will lead to a globally optimal outcome.

Think of it like organizing a single parking space for multiple cars that arrive at different times. Each time a car arrives, you park the one that arrives first and remove any that cannot fit without overlapping. If you consistently park the arriving cars that fit best based on their order, you can maximize the number of cars parked through the day.

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 a counterexample...

One common misguided strategy is to prioritize slots based on which one starts the earliest. This might seem logical, but there can be instances where an early-starting slot is long and thus prevents other shorter slots from being utilized. In fact, prioritizing merely based on starting time could lead to a situation where fewer teachers can use the room overall.

Imagine a restaurant with only one table open for reservations. If you fill that table with a long reservation for a single group at the beggining of the night, you might not have any table left for smaller groups who could have dined in between those long timings. The result is fewer total diners accommodated.

Another greedy strategy we might think of is to choose a booking whose interval is shortest. Once again here is a counterexample...

Another pitfall is to choose the shortest interval booking first. While you might think selecting the shortest time would allow more bookings to fit, it can rule out multiple other overlapping bookings, leading to a suboptimal total count of scheduled teachers. It's crucial to realize that the overall schedule needs to be maximized rather than just minimizing one single slot.

Think about filling jars of different sizes with marbles. If you always choose the smallest jar first (because it’s the shortest), you may miss opportunities to use larger jars that could hold more marbles. By blindly following the idea of using the shortest option, you end up with less overall capacity.

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...

The most effective greedy strategy identified is to select the booking with the earliest finish time. This is because it leaves the maximum remaining time for subsequent bookings, thus increasing the chances of accommodating more slots. Proving that this strategy works involves showing that the scheduling yields an optimal number of non-conflicting bookings.

Consider a race track where runners can only run one by one. If you allow the current runner to finish as soon as possible and then allow the next to start right after, you maximize the total number of laps completed instead of letting someone start immediately, which may block more laps overall.

Before we prove it, let us formally write down the algorithm a little more clearly. So, we start with the set of bookings B and we want to construct from this set, a subset A of accepted bookings...

The algorithm comprises selecting bookings based on the sorted order of their finishing times. Initially, no bookings are accepted, and from the remaining bookings, the algorithm picks the one with the shortest finish time, then removes those that overlap with it. This process continues until no more bookings are left to choose from...

Think of a job scheduler where each job must finish to allow the next to begin. If you always pick the job due to finish the earliest, you continually make room for more jobs to be done, maximizing workplace efficiency. This can be visualized as a chain where one link completing allows the next to fit in snugly.

--