19.4.2.1. Initial Condition

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.

A greedy algorithm approaches problem-solving by making decisions that seem to be the best at the moment—these are called 'local criteria.' The crucial aspect of this strategy is that once a decision is made, it is not reconsidered. This can significantly narrow down the number of possible solutions as it strategically eliminates some paths early on. However, it's important to note that this strategy may not always yield the best overall solution (the global optimum). Therefore, it's vital to validate that the decisions made lead to the best possible outcome.

Imagine you are trying to pack a suitcase for a trip. You have many items to choose from, but you decide to take only the items that fit best in the suitcase right now. You don’t reconsider or go back to swap items if you find some other items would fit better. This can lead to a situation where you may not have packed the most useful or necessary items for your trip.

So, 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 claimed that this would in fact be the shortest distance to that vertex from the source.

Dijkstra's algorithm exemplifies a greedy algorithm by progressively determining the shortest paths from a source node to other nodes. It 'burns' or marks nodes as visited while keeping track of the shortest distances to untouched nodes. Each time a new node is visited, the shortest distance to that node is finalized, ensuring that the overall path found is indeed the shortest possible. This algorithm effectively combines local choices (shortest current distance) to achieve a global optimum (overall shortest path).

Think of navigating a city using a map. You always choose the shortest route to your destination at each intersection based on the map in front of you, marking the path as you go. Despite focusing on local choices at each intersection, this method helps ensure you arrive at the fastest route possible to your final destination.

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.

The interval scheduling problem involves scheduling different activities (or lectures in this case) where each activity has a start and finish time. The challenge is to choose a set of non-overlapping activities (or bookings) to maximize the total number of activities scheduled. This can be visualized as assigning time slots to teachers without conflicts, ensuring that no two teachers have overlapping classes.

Picture a conference room where multiple teams want to hold meetings. Each team has its preferred time slot, but some overlap. The goal is to schedule as many meetings as possible without overlap, where selecting a time slot aligns with ensuring that other teams can still hold their meetings. Good scheduling can allow several teams to benefit from using the same space efficiently throughout the day.

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.

In this greedy approach to interval scheduling, the strategy involves selecting an available booking based on a local criterion, such as the earliest finishing time. Once a booking is selected, any conflicting bookings that overlap with this chosen booking are removed from consideration. This ensures that each selection progresses without conflicts. The strategy aims to maximize the total number of bookings by iteratively making the best choice available at each step.

Like planning a family reunion, where you must select a time slot that works for the most relatives. Each time you choose a slot based on who is available (the earliest finish), you ensure that no two relatives overlap, making the most of everyone's availability and maximizing attendance.

--