19.3.2. Greedy Approach Overview

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. 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 we never go back and revise an earlier decision.

Greedy algorithms are a type of algorithm used in optimization problems. The main idea behind them is to make the best choice at each step without reconsidering previous choices. This approach is beneficial because it simplifies the problem-solving process by reducing the complexity of the search space. However, it is important to note that greedy algorithms do not always guarantee the best overall solution; they can lead to a suboptimal solution in some cases.

Think of making change for a dollar using the fewest coins possible. If you have coins of 25 cents, 10 cents, 5 cents, and 1 cent, a greedy algorithm would start by taking the largest coin that is less than or equal to the remaining amount. This means starting with coins of 25 cents first until you cannot take another without exceeding a dollar. While this may often yield the best solution, there can be cases where other combinations of smaller coins yield fewer coins overall.

We have seen three algorithms so far which follow this paradigm. The first was Dijkstra’s algorithm for the single source shortest path problem. 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 be the shortest distance to that vertex from the source.

Dijkstra's algorithm is a famous example of a greedy algorithm. It operates by maintaining a set of vertices whose shortest distance from the source is known. After selecting a vertex, it calculates the distance to its neighbors and updates their distances. This process continues until all vertices have been processed. The greedy nature lies in the fact that once a vertex's shortest distance is determined, it is not reconsidered, ensuring that the algorithm focuses only on optimizing the immediate choices.

Imagine you're trying to find the quickest route to a series of destinations. Each time you reach a destination, you choose the next closest location without reevaluating your past choices. This is similar to how Dijkstra’s algorithm selects the nearest vertex, ensuring that the overall path remains the shortest possible from your original point.

Now let us look at a completely different problem called interval scheduling. Suppose we have a special video classroom, where we can deliver online lectures. 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 task is to look at the set of bookings and choose a subset which is feasible, that is, no two bookings that we choose interfere with each other.

The interval scheduling problem exemplifies the greedy approach perfectly. The goal is to maximize the number of non-conflicting bookings. To achieve this, a greedy strategy would involve selecting the booking that ends the earliest — this choice allows the maximum remaining time for future bookings. This ensures that you can fill the classroom with as many instructors as possible within the available time slots.

Consider a busy conference room where multiple meetings are requested. If you want to maximize the number of meetings that can occur in that room, you would schedule the meeting that ends the soonest first. This way, you leave the most room for additional meetings, accommodating more requests than if you prioritized longer meetings.

Here is a fourth strategy, instead of choosing the one with the earliest start time, let us choose the one whose finishing time is earliest. This strategy works, and we can prove it. As long as we have pending bookings which are still feasible, we pick the booking which has the smallest finishing time.

Choosing the earliest finishing time as a criterion allows for maximizing the room usage by ensuring that once one booking ends, the next possible booking can be accommodated immediately. The greedy strategy here is based on filling up availability quickly by first choosing shorter engagements. This can often lead to an optimal solution where the maximum number of teachers can use the classroom.

Imagine you're organizing a series of quick appointments throughout the day. By starting with appointments that are brief and end quickly, you can fit in as many as possible rather than lingering on longer sessions that would limit the number of short meetings you can hold consecutively.

Let us just quickly look at how we would implement this and estimate the upper bound of the complexity. Initially, we sort the m bookings by finishing time, this takes time n log n for n bookings, and we can then scan through the sorted list to extract the maximum number of non-overlapping bookings.

The greedy algorithm for interval scheduling first requires sorting the bookings by their finish times, which takes O(n log n) time. After sorting, the algorithm can then proceed in linear time, O(n), to scan through the sorted list and select the maximum feasible bookings. Therefore, the overall complexity of the greedy scheduling algorithm is O(n log n), mainly driven by the sorting step.

Think of a teacher scheduling classes: first, they gather all possible class times and sort them based on when they end. After sorting, the teacher methodically checks through the schedule, choosing classes to fit into their timetable based on the earliest finishing classes available, ensuring they optimize their teaching slots efficiently.

--