19.4.2.2. Selection Process

Let us take another look at greedy algorithms. (Refer Slide Time: 00:05)

So, we are looking at algorithms where we need to achieve a global optimum by making a sequence of choices. So, in a greedy strategy what we do is we make the next choice based on some local criteria. So, there may be a number of choices we could make, but we just pick one of them based on something which looks good at the moment and now we never go back and revise an earlier decision.

Greedy algorithms work by making a series of decisions where each decision is made based on what seems best at that moment, without considering the overall context. The idea is to make local optimal choices in hopes that these will lead to a global optimum solution. However, this approach may not always lead to the best solution, which is why it is crucial to prove that local choices contribute to the best overall outcome.

Imagine you're at a buffet with various delicious dishes, and you're trying to decide what to eat. You might pick the dish that looks the most appealing in that moment, like a beautiful piece of cake, thinking it will satisfy your hunger. If you keep choosing the most appealing dishes without considering your overall meal, you might end up too full to enjoy the healthy options, missing out on a well-balanced meal.

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. So, recall that in this algorithm we kept burning vertices and at each stage we froze the distance to the nearest unburnt vertex and claim that this would in fact be the shortest distance to that vertex from the source.

A closely related algorithm is Prim’s algorithm for the minimum cost spanning tree. So, here we incrementally build up a tree and at each stage we add to this spanning tree, the nearest vertex that is not yet in the tree. And here the global optimum that we achieved is that we construct the spanning tree that is minimum cost. Another algorithm for a minimum cost spanning tree is Kruskal’s algorithm.

The section discusses three algorithms that utilize a greedy approach. Dijkstra’s algorithm finds the shortest path from a source to other vertices by iteratively selecting the shortest distance available and 'freezing' that vertex to avoid revisiting it. Prim's algorithm builds a minimum spanning tree by at each step adding the closest vertex not yet included. Meanwhile, Kruskal’s algorithm builds a minimum spanning tree by adding edges that connect different components without forming cycles, selecting the smallest edges first.

Think of planning a road trip. If you want to reach multiple destinations, Dijkstra’s algorithm is like choosing the most efficient route to each location without backtracking. Prim's algorithm is similar to constructing a road network where you keep adding the shortest new roads connecting towns. Kruskal’s method can be visualized as gathering different paths into one connected area while ensuring no loops form, ensuring that every town is reachable without redundancy.

Now let us look at a completely different problem, a problem called interval scheduling. 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.

This part of the section introduces the problem of interval scheduling, where multiple instructors want to use the same classroom for their lectures. Each instructor has a preferred time slot that they would like to book, but these slots might overlap with one another. The objective is to choose a subset of these slots that do not interfere with each other, thereby maximizing the number of instructors who can use the classroom.

Imagine scheduling multiple meetings in a conference room where each team leader wants to present their update. If two meetings overlap, only one can occur at a time. You must carefully select which meetings can happen so that you can have as many as possible without conflicts, similar to coordinating schedules in a busy office.

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. This sequence of bookings that we are choosing maximizes the number of teachers who get to use the room.

The greedy approach for the interval scheduling problem involves choosing one time slot at a time based on certain criteria. Once a booking is selected, any conflicting slots are removed from consideration, as they cannot be scheduled at the same time. Despite potential intuition on selecting slots, one must find an optimal strategy that truly maximizes usage of the room.

Think about organizing film screenings at a small theater. If you choose the first movie that requests a screening slot without checking if other popular films can fill those slots better, you might leave gaps that could have been filled by more films, leading to lost opportunities for showing various films. A strategic approach can help optimize the number of films shown.

So, let us look at some typical greedy strategies that one might want to think of. So, one strategy might be to choose the booking whose start time is earliest, but it is not difficult to come up with a counter example. If we look at this picture, there is one long green booking that starts earliest and ends after all the other bookings are made. So, if we use this greedy strategy we would allocate this very long booking and the entire period it will be allocated to just one teacher.

In evaluating potential greedy strategies, choosing the earliest start time is not always effective. This chunk emphasizes that while it may seem logical to pick the earliest time, it could lead to poor outcomes like using up the entire available time slot for one instructor rather than maximizing the overall number of instructors that can use the classroom.

Imagine a party organizer making a schedule for events. If they book the first performer they contact without considering how long they will take or if they can fit in more acts, they risk missing out on a lineup that could entertain more guests with shorter, more diverse performances.

So, here is a fourth strategy, instead of choosing the one whose start time is earliest, let us choose the one whose finished time is earliest. So, can we come up with a counterexample or should we instead try to prove this is correct? So, in fact, this strategy does work.

The text introduces a successful greedy strategy based on selecting the booking with the earliest finish time instead of the start time. This method proves effective, and there’s an assertion that this can be shown to always yield an optimal solution. By focusing on finishing times, one can leave more room for subsequent bookings.

Think of a restaurant that schedules dining tables. If diners finish their meals quickly, allowing for quick turnaround, the restaurant can seat more customers throughout the night. By prioritizing customers who will leave the soonest, they maximize diner turnover, similar to scheduling teachers in the classroom.

--