19.3.3. Greedy Strategies

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

Greedy algorithms aim to find the best overall solution by making a series of local decisions. Each decision is made by selecting what appears to be the best option at that time, without reconsidering past choices. This method simplifies the problem-solving process and narrows down potential solutions, but it doesn't always lead to the optimal solution for every problem.

Imagine you're hiking in a forest and need to choose among various paths. A greedy strategy would involve always choosing the path that seems most promising at each intersection, like the one that appears to lead downhill. While this may lead you to a nice view, it might not be the best overall route to your destination.

We have seen three algorithms so far which follow this paradigm. The first was Dijkstra’s algorithm for the single source shortest path problem, where we keep burning vertices and at each stage freeze the distance to the nearest unburnt vertex. Prim’s algorithm increments builds up a tree by adding to it the nearest vertex not yet in the tree. Kruskal’s algorithm collects edges that do not form a cycle to construct a minimum cost spanning tree.

This chunk describes three examples of greedy algorithms. Dijkstra's algorithm finds the shortest path from a source to other vertices in a graph by systematically selecting the nearest unvisited vertex. Prim's algorithm builds a minimum spanning tree by always adding the closest vertex not yet included. Kruskal's algorithm similarly constructs a minimum spanning tree but by selecting the smallest edges that don't create a cycle.

Think of Dijkstra's algorithm like a delivery service trying to find the quickest route without backtracking. Each time they reach a new location, they assess which nearby location can be reached most quickly without traversing previous paths. Prim's and Kruskal's analogies can be thought of as assembling a network of roads where Prim's focuses on building the road connections one segment at a time while Kruskal's approach gathers all potential roads first, ensuring no overlaps.

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, each having a start and finish time for their lecture. Our task is to choose a subset of these bookings such that no two bookings interfere with each other while maximizing the number of teachers who get to use the room.

The interval scheduling problem involves managing resources for multiple tasks that have time constraints, which is a common real-world scenario. In this case, we need to allocate a limited resource (the classroom) to different users (teachers) based on their desired time slots, ensuring that overlapping bookings are avoided. The aim is to maximize usage by selecting the largest feasible schedule.

Imagine a movie theater trying to schedule different movies in the same auditorium. The theater wants to show as many films as possible in a single rotation of the auditorium while ensuring that no films overlap. Each film's start and end times act like the teachers’ bookings and need to be carefully selected to accommodate the maximum number of screenings.

If we follow a greedy approach for interval scheduling, we might pick the booking whose start time is earliest. However, this could lead to suboptimal solutions. For example, if we choose a long booking that starts earliest, we may end up blocking the schedule for other teachers, leaving fewer total bookings. Similarly, choosing the shortest interval could also leave us with fewer bookings.

This chunk critiques naive greedy strategies for booking selection. Simply choosing the earliest start or the shortest interval isn't effective, as they may block out larger possibilities for usage. The examples illustrate how local maximum choices can lead to poor overall outcomes, emphasizing the need for smarter strategies.

Consider planning your day with various appointments. If you blindly choose the first available slot without considering duration or subsequent schedules, you might end up with large gaps in your day or overlapping commitments. A better approach would be to compare all available slots to maximize your time.

A successful strategy is to choose the booking whose finish time is earliest. This choice can be proven effective. We begin with the set of bookings and construct a subset of accepted bookings by always picking the one that finishes first and removing all conflicting bookings.

The principle of choosing the booking with the earliest finish time is efficient because it frees up time for subsequent bookings. This approach provides a systematic way to build an optimal set of non-overlapping bookings. The explanation demonstrates how systematically picking bookings based on their finishing times guarantees that we maximize their use without conflict.

Think of a restaurant trying to seat as many customers as possible. A smart approach would be to quickly clear a table (booking) that finishes its meal earliest, allowing the next group to be seated right away. This ensures the restaurant has a steady flow of diners rather than long waits between meals.

--