19.3.5. Optimal Strategy and Algorithm

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 is a method for solving optimization problems by selecting the best available option at each decision point without reconsidering previous choices. This means that at every step, you focus on what seems best locally, aiming for the best global outcome. However, it's crucial to note that greedy algorithms don’t always lead to a globally optimal solution, so it's important to prove their effectiveness for the specific problem.

• Chunk Title: Examples of Greedy Algorithms
• Chunk Text: So, we have seen three algorithms so far which follow this 3D paradigm. The first was Dijkstra’s algorithm for the single source shortest path problem. The second is Prim’s algorithm for the minimum cost spanning tree. The last one is Kruskal’s algorithm.
• Detailed Explanation: Dijkstra’s algorithm is used to find the shortest path from one node to all other nodes in a graph. It progressively 'burns' or explores nodes, making local choices based on the shortest known distances. Prim’s algorithm and Kruskal’s algorithm are both used to construct minimum spanning trees. Prim’s algorithm builds the tree incrementally by adding the nearest vertex while Kruskal’s approach adds edges while avoiding cycles. Each of these algorithms exemplifies how a greedy strategy can yield optimal results in specific contexts.
• Chunk Title: Interval Scheduling Problem Definition
• Chunk Text: Now let us look at a completely different problem, a problem called interval scheduling. 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.
• Detailed Explanation: The interval scheduling problem involves managing various requests for time slots in a way that maximizes usage without overlap. Each instructor has a specific time interval—start and finish times—for their lecture that may conflict with others. The objective is to select a set of bookings such that no two bookings overlap, thereby maximizing the number of teachers who get to use the room.

Imagine a shared conference room in an office where multiple teams want to present their work. Each team has a 1-hour slot they prefer, and some teams' slots overlap. The goal is to schedule presentations without double-booking the room, allowing as many teams to present as possible.

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.

To implement a greedy approach in interval scheduling, you would first select the booking with the earliest finishing time from the options available. After selecting a booking, you need to eliminate any overlapping bookings since they cannot be scheduled simultaneously. The process involves making choices that seem best at each step based on a local optimum. However, it is necessary to prove that this strategy leads to the global optimum.

Think of a person planning their day. They will book appointments sequentially, always picking the earliest finishing meeting next, which allows room for more meetings throughout the day rather than allowing long meetings to block out time.

Let us look at some typical greedy strategies that one might have thought of. One strategy might be to choose the booking whose start time is earliest, but it is not difficult to come up with a counterexample.

It's critical to evaluate if a greedy choice is indeed optimal. For example, if you select the booking that starts earliest, you may inadvertently occupy a time slot that prevents several others from being scheduled. Counterexamples help illustrate scenarios where initial local optima may mislead toward a suboptimal global result. Thus, not all greedy strategies work for the interval scheduling problem.

Imagine a person trying to fill their day by picking the first appointment they see on a calendar. If that appointment is a long one, it could block other shorter appointments that could provide a more productive day overall.

So, here is a fourth strategy, instead of choosing the one whose start time is earliest, let us choose the one whose finished time is earliest. So, can we come up with the counterexample or should we instead try to prove this is correct. So, in fact this strategy does work and let us see how we can prove it.

The strategy of selecting the booking with the earliest finishing time is proven to be effective for the interval scheduling problem. This method ensures that after selecting an appointment, the remaining time for other appointments is maximized. Proving this strategy's correctness is often done by induction, showing that with each selection, you enable the greatest potential for future bookings.

Picture organizing multiple trips for a tour. By letting the first trip return earliest, you can fit in multiple more trips (or activities), keeping the itinerary full and satisfying all customers rather than blocking longer slots that crowd out other options.

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. So, initially, we sort the m bookings by finishing time, this takes time n log n for n bookings.

The algorithm can be implemented by first sorting the bookings based on their finishing times, which takes O(n log n) time. After sorting, a linear scan is performed through the bookings to select those fitting the greedy criteria. The overall time complexity remains efficient at O(n log n), making this approach effective for larger datasets.

Imagine organizing the schedule of events for a conference. Sorting the presentations by end time allows the organizer to quickly determine the best order of sessions, without needing to re-arrange them repeatedly, thus streamlining the scheduling process.

--