19.5. Proof of Correctness

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, the maybe somebody who wants the slot like this, so the blue slot starts before the red slot ends, so obviously both these slots cannot be in given bookings, because there were interfere with each other. So, our task is to look at the set of bookings and chooses 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.

In the context of interval scheduling, we're faced with a situation where multiple instructors want to book a time in a classroom for their online lectures. Each instructor has a specific time slot defined by a start time (s[i]) and an end time (f[i]). The challenge here is that two bookings cannot overlap—if one instructor's lecture slot overlaps with another's, they cannot both be scheduled. Therefore, the objective is to select a set of non-overlapping bookings that maximizes the number of teachers using the classroom. This introduces the concept of a feasible subset, which allows us to utilize the room effectively.

Imagine a busy conference room where several presenters want to give their presentations. Each presenter needs a certain time slot, but if their slots overlap, they can't present at the same time. To make the best use of the conference room, the manager needs to schedule the events so that as many presenters as possible can speak without any overlaps. This scheduling problem is similar to the interval scheduling problem we are discussing.

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.

To tackle the interval scheduling problem with a greedy approach, we start by selecting one of the available bookings based on a specific criterion—this is our greedy choice. After choosing a booking, we then eliminate all bookings that overlap with the chosen one, as they cannot be scheduled together. The challenge lies in justifying that this method of choosing bookings will truly maximize the number of teachers who can use the room. Essentially, we are aiming to make a series of good local decisions that will lead to the best overall outcome.

Think of a carpool scheduling system. Each person has a specific time they need to leave for work. The coordinator selects the earliest known departure time in hopes of finding others who can ride together. Once a time slot is chosen, any additional riders whose schedules overlap with the selected departure time are excluded to avoid conflicts. Despite best efforts with these quick local decisions, we must ensure these choices lead to the highest number of carpools.

So, let us look at 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. So, can we come up with the counter example or should we instead try to prove this is correct? So, in fact this strategy does work and let us see how we can prove it.

This strategy proposes that rather than choosing the booking with the earliest start time, we select the one with the earliest finishing time. This approach intuitively makes sense, as by choosing a booking that finishes quickly, we leave more room for other potential bookings afterward. The goal here is to establish whether this method will successfully yield an optimal solution for the interval scheduling problem. It requires proof to show that this solution is indeed valid and maximizes usage of the room.

Consider a read-a-thon event with various readers who each have a time limit for how long they can read their selection. If we allow the person who can finish reading the quickest to go first, this leaves room for more readers to fit into the schedule after them. This contrasts with the idea of picking the one who starts first, which may block other readers due to overlapping times.

So, having shown that the greedy strategy always stays ahead, we will now claim that actually our solution must be optimum. So, suppose that m is actually strictly greater than k, then we know that when we reach i k, it is before j k. Now, because we have a solution which is longer than k, there is another job after this called j k plus 1, assuming that m is strictly greater than k. So... Therefore, we cannot have any bookings in the optimum solution which go beyond k and therefore, m must be equal to k.

In proving the correctness of our greedy strategy, we argue that the solution it produces is optimal by establishing a relationship between our selected set of bookings and any potential optimal set. If the optimal set O has more bookings than our greedy solution, then logically, there should be a booking in O that could not have been selected while processing our greedy algorithm, leading to a contradiction. Hence, we conclude that the number of bookings selected by our greedy strategy should match that of the optimal solution.

Imagine a game where participants are trying to collect points by choosing their moves. If one strategy clearly allows more points based on the game's rules, then any alternative approach that tries to gather even more points must inevitably conflict with previously made choices. The essence of the proof is like saying, 'If our method leads to maximum points, then no other approach can exceed that without violating the game's rules.'

So, having shown that it is correct, let us just quickly look at how we would implement this and estimate the upper bound of the complexity.

The algorithm to implement the greedy strategy involves sorting the bookings by their finishing time, which typically requires O(n log n) time. After sorting, we iterate through the list of bookings, efficiently selecting compatible bookings. This scanning through choices ensures that we adhere to the non-overlapping condition by checking the start time against the last chosen booking's finish time. Overall, the algorithm runs in O(n log n), taking into account the sorting and the linear pass through the bookings.

Think of scheduling a series of appointments for a doctor. First, the assistant organizes all appointment requests by their ending times, ensuring no two patients are scheduled at the same time. This process makes efficient use of the day while minimizing wait times. The complexity of sorting and placing appointments parallels the algorithm's processing efficiency.

--