19.6. Complexity Analysis

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.

In greedy algorithms, the goal is to find the best possible solution by making a series of choices that seem optimal at each step. This means that rather than considering the larger context (or global optimum), we rely heavily on local optimum criteria—essentially making the most 'locally' beneficial choice available at that moment. A significant aspect of greedy algorithms is that once a decision is made, it's final; we do not reconsider previous choices. This approach dramatically narrows down the search space of potential solutions, but it's important to note that not every greedy approach leads to the best overall solution. Therefore, when using such strategies, one must verify that these local choices culminate in a global optimum.

Imagine you are climbing a hill. At each step, you look around to find the steepest path in front of you that allows you to ascend higher. However, there might be times when taking a smaller incline (a local optimum) would give you an easier route to reach a higher elevation (the global optimum). The greedy approach focuses on making the best step at each moment without considering the entire journey.

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. A closely related algorithm is Prim’s algorithm for the minimum cost spanning tree. Another algorithm for minimum cost spanning tree is Kruskal’s algorithm.

Three key algorithms demonstrating the greedy approach are Dijkstra's, Prim's, and Kruskal's algorithms. Dijkstra's algorithm is used to find the shortest path from a starting point to all other vertices in a graph, effectively 'burning' vertices to keep track of the shortest routes determined so far. Prim's and Kruskal's algorithms are both used for finding the minimum cost spanning trees but take different approaches: Prim's builds the tree incrementally by adding the nearest vertex, while Kruskal’s focuses on adding the smallest edges without forming cycles. Each algorithm highlights how greedy choices can lead to optimal solutions in specific scenarios.

Think of Dijkstra's algorithm as a GPS system that helps you find the shortest route to your destination. It calculates progressively the shortest distance to every point on your way. Prim's and Kruskal's algorithms can be likened to planning a road trip where you want to minimize the toll costs on your route—while one focuses on taking the cheapest road at each juncture (Prim's), the other gathers the cheapest segments first without forming loops (Kruskal's).

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 managing time slots for various instructors wishing to use a shared resource (like a classroom). Each instructor has a specific time they wish to book, and the challenge lies in selecting the maximum number of non-overlapping bookings from a set of conflicting requests. This is a classic example of how greedy strategies can be applied to solve scheduling problems effectively by picking the most beneficial current option in terms of availability.

Imagine a popular community center that only has one room available for classes. Teachers want to schedule their sessions, each with specific start and end times. If two teachers overlap their schedules, one will have to wait. The goal is to help as many teachers as possible use the room throughout the day without conflicts.

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. One strategy might be to choose the booking whose start time is earliest, but it is not difficult to come up with a counterexample.

Using greedy strategies to select bookings blindly based on the earliest start or shortest duration often leads to suboptimal solutions. Early selections might block out potential subsequent bookings that could have utilized that time more efficiently. The failure of early start strategies highlights the inherent risk of making local optimal choices without considering their long-term impact.

Think about a pizza restaurant. If they choose to only sell the first order that comes in without considering how many more orders they can fulfill later, they may find themselves missing out on potential larger orders that could have come later. By filling the first order, they may have blocked the kitchen from maximizing their output.

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

Opting to select bookings based on the earliest finish time is a successful greedy strategy. By focusing on finishing sooner, the algorithm can free up space for more potential bookings, allowing the algorithm to fit in the maximum number of classes. This method has been proven effective as it ensures that once a booking is accepted, it creates opportunities for additional bookings.

Similar to a Tetris game, where you must clear out rows to make room for more blocks. By placing the blocks (or bookings) that fit best in empty spaces (or available time slots), you can maximize your performance. Choosing time slots that end sooner allows for more classes to be scheduled, just as clearing rows allows you to keep playing longer in Tetris.

So, our goal is to show that the solution A produced by our algorithm is actually correct. So, suppose there is an optimal set of bookings O, now we cannot in general assume that our solution A is identical to O.

To validate the effectiveness of the chosen greedy strategy, we examine whether the number of accepted bookings (set A) matches or is less than that of any optimal solution (set O). The proof relies on establishing that as bookings are selected based on the earliest finish time, they do not conflict with those in the optimal set of bookings, thus indicating that A can hold as many or more bookings as O. This method hinges on induction and demonstrates the consistency of the greedy approach in achieving an optimal solution.

Imagine a team of sports players who need to arrange matches without conflicts. If one player books a field that finishes at a certain time, another player can also get a slot afterward, thus maximizing the use of the field. The aim is to prove that every time we make a booking with an earlier finish, we leave enough room for further bookings—the same principle can apply to other scheduling issues.

So, having shown that it is correct, let us just quickly look at how we would implement this and estimate the upper bound of the complexity.

The complexity analysis of the greedy algorithm for interval scheduling typically involves an initial sorting step of all the bookings based on their finish times, which incurs a time complexity of O(n log n). Following this, a linear scan of the bookings checks for conflicting times while selecting valid bookings, yielding an additional O(n) complexity. Thus, the total complexity remains dominated by the sorting step, yielding a final complexity of O(n log n). This makes the greedy approach both efficient and effective for solving the interval scheduling problem.

Think of organizing a music festival. Initially, you would sort performers based on their required stage time (like booking end times). Then, using simple logic, you decide who plays when without overlaps. The most time-consuming part is figuring out schedules, after which it’s easy to tweak the performance slots. The overall planning process is much like executing a well-designed algorithm.

--