19.1.1. Greedy algorithms: Interval scheduling

Let us take another look at greedy algorithms. So, we are looking at algorithms where we need to achieve a global optimum by making a sequence of choices. In a greedy strategy, we make the next choice based on some local criteria. This means that we might have several options, but we pick one based on what seems best at the moment, and we never go back to revise an earlier decision. This approach drastically reduces the space in which we have to search.

Greedy algorithms work by making the best local choice at each step with the hope of finding a global optimum. This means that instead of evaluating all possible solutions to find the best one, we take the first option that looks best based on current information and proceed with it. The algorithm only chooses the next step based on the current situation, without re-evaluating previous choices. However, it's important to verify that this method leads to an optimal overall result, as greedy strategies can often fail to find the best solution.

Imagine you are at a buffet with various food options. Your strategy is to choose the dish that looks most delicious at each moment without considering the overall meal plan. You might end up filling your plate with desserts first, thinking they are the best choice at that moment, but later regret not leaving space for the main course. Just like in greedy algorithms, this approach might not yield the best overall experience.

We have seen three algorithms so far which follow this greedy paradigm. The first was Dijkstra’s algorithm for the single source shortest path problem. The second is Prim’s algorithm for the minimum cost spanning tree, and the third is Kruskal’s algorithm, which collects edges to form a tree.

Dijkstra’s algorithm efficiently finds the shortest path from a single source to all other vertices in a graph by 'freezing' the shortest distance to vertices as they are explored. Prim’s algorithm builds a minimum spanning tree by always adding the closest vertex not yet included in the tree. Kruskal’s algorithm, on the other hand, adds the lowest-weight edges to a growing forest of trees, ensuring no cycles are formed. Each of these algorithms illustrates how local choices can lead to an optimal global result within their respective contexts.

Think of Dijkstra’s algorithm as a delivery driver who wants to find the quickest route to deliver packages across a city. At each intersection, they assess the shortest path to the next delivery point, ensuring they always pick the optimal route at every turn, which ultimately leads them to complete all deliveries in the least time.

Now, let us look at a completely different problem called interval scheduling. Suppose we have a special video classroom where different teachers want to book the slot for lectures. Each instructor has a time slot from s_i to f_i, and two instructors may have overlapping slots. Our task is to choose a subset of bookings such that no two chosen bookings interfere with each other while maximizing the number of teachers who can use the room.

In the interval scheduling problem, the goal is to select a maximum set of non-overlapping time intervals from a collection. Each time interval corresponds to a booking request for a specific time, and overlapping intervals cannot both be scheduled. By selecting intervals wisely, we can accommodate as many requests as possible within the constraints of time overlaps, aiming for optimal usage of the available space.

Imagine scheduling appointments in a doctor's office. Each patient has a specific time for their visit, and some may overlap. The doctor’s goal is to fit in as many patients as possible without making them wait. By carefully scheduling, the doctor can ensure that each patient gets their time slot while maximizing the number of patients treated in a day.

If we follow a greedy approach, we would pick the booking with the smallest finishing time among pending bookings. Once a booking is selected, we remove all conflicting bookings from our list, and this process continues until there are no more bookings left.

In applying the greedy strategy to interval scheduling, the algorithm selects the booking that ends the earliest, thereby allowing more time for potential future bookings. When a booking is chosen, all subsequently overlapping bookings are discarded from consideration. This step-by-step selection process aims to maximize the number of bookings without overlaps, achieving an efficient schedule.

Think of it like a game day schedule. You want to pack as many matches as possible in one arena. By selecting the match that finishes first, you create a gap for a new match to start right after. Each time you schedule a match, you take away the time slots that would interfere with other potential matches, ensuring the arena is used to its maximum capacity.

Some potential greedy strategies include choosing the booking with the earliest start time or the shortest interval. However, these strategies may not yield optimal solutions. For instance, selecting the earliest start time may reserve a long block of time for a single booking, preventing other bookings from being scheduled.

While it might seem logical to choose the booking that begins first, this greedy strategy can prevent the scheduling of multiple shorter, non-overlapping bookings. Similarly, selecting the shortest booking could lead to conflicts with other potential bookings. Therefore, careful consideration is required to determine which booking strategy produces the best results in terms of maximizing the number of successful allocations.

Imagine a movie theater trying to schedule films. If the theater chooses to show the longest film first because it starts earliest, it may block out time for shorter films that could have been shown back-to-back later, leading to fewer total films being screened in a day.

A successful strategy is to choose the booking whose finished time is earliest. We will provide a proof to argue that this strategy works effectively.

By selecting the booking that finishes earliest, the algorithm ensures that it leaves the maximum possible time for subsequent bookings. This greedy choice creates the best chance to fit more non-overlapping intervals. The proof involves induction, showing that our greedy selections stay ahead of any other choices made based on different strategies by ensuring that they do not conflict with each other.

This strategy can be compared to filling a parking lot. By letting the cars that plan to leave first (those that finish their stay earliest) park first, the lot minimizes congestion and maximizes the number of cars that can fit throughout the day.

To implement this algorithm, we begin by sorting the bookings based on their finishing time. We then proceed to select bookings using a single scan, resulting in a time complexity of O(n log n).

The implementation involves two main steps: sorting the list of booking intervals based on their finish times, which takes O(n log n) time, followed by a linear scan to select the maximum set of compatible bookings. The efficiency of this algorithm stems from the fact that once sorted, the selection process becomes straightforward, ensuring a quick determination of overlapping intervals.

Consider how a restaurant organizes its tables for reservations. First, they arrange their bookings by time. Then they can easily go through and allocate tables to each reservation one by one, ensuring not to double book any table. This streamlined process allows for effective management without confusion.

--