19.1. Design and Analysis of Algorithms

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 maybe 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 work by making a series of decisions that seem best at the moment, without looking ahead or backtracking. For example, if you are trying to reach the top of a hill, you might decide to move in the direction that looks most upward—even though this could lead you off the best path if you don't consider future choices.

Imagine you are packing a suitcase for travel. You might choose the clothes that take up the most space and look the most appealing first. This may leave little room for essential items later. A better approach would consider total space and importance of items before deciding which to pack.

We have seen three algorithms so far which follow this greedy paradigm: Dijkstra’s algorithm for the single source shortest path problem, Prim’s algorithm for the minimum cost spanning tree, and Kruskal’s algorithm.

Dijkstra’s algorithm helps find the shortest paths from one vertex to all other vertices in a graph. Prim’s algorithm builds a minimum spanning tree by adding the cheapest available edge that connects the tree to a new vertex. Kruskal’s algorithm collects edges in order of weight and adds those that will not create a cycle. Each of these utilizes local optimal choices to find a global best.

Consider planning a road trip where you want to find the quickest route. Dijkstra’s algorithm tells you how to reach multiple destinations directly from your starting point while Prim’s algorithm selects the best networks of roads to connect cities with minimum tolls.

Let us look at a problem called interval scheduling. Suppose we have a classroom where different teachers want to book slots to deliver lectures. Each instructor has a time slot starting at s_i and finishing at f_i. The task is to choose a subset of bookings that do not overlap, thereby maximizing the number of teachers who can give classes.

In the interval scheduling problem, we must select time slots that do not conflict with each other. For instance, if Teacher A's timing intersects with Teacher B's, only one can be booked for that slot. Our objective is to find the maximum number of non-overlapping classes.

Think of it like scheduling meetings in a conference room. If two teams want to meet at the same time, it’s crucial to find a schedule that accommodates as many teams as possible without overlapping meeting times.

Broadly if we follow a greedy approach, we would pick one booking based on local criteria, then remove all conflicting bookings. Typical greedy strategies such as choosing the booking with the earliest start time may not yield optimal results.

While it might seem effective to select the earliest start time, it could lead to conflicting bookings later. Instead, the goal is to maximize the overall bookings rather than just picking the first one that fits a criteria.

Imagine a bus schedule where several buses might want to leave at the same time. Choosing one bus just because it fits first doesn’t consider the overall efficiency of bus scheduling which might allow more buses to leave if one starts later.

A fourth strategy is to choose the booking whose finishing time is earliest. This can be shown to work by proving it effectively maximizes the number of non-overlapping bookings.

By consistently choosing the booking with the earliest finish time, we leave maximum room for subsequent bookings. This ensures that each selected booking allows as many following bookings as possible without conflicts.

This is like choosing supermarket checkout lines—selecting the line that is moving the fastest (or has the fewest customers) means you get through the line as quickly as possible and can start shopping sooner.

--