Greedy Algorithms: Activity Selection & Fractional Knapsack

1. The Greedy Paradigm: A New Way of Thinking

Dynamic Programming finds the optimal solution by solving all subproblems and combining their results. Greedy algorithms take a more direct path. At each step, they make a choice that seems best at that moment, without worrying about future consequences.

This might sound shortsighted, and indeed, for many problems (like the 0/1 Knapsack or Matrix Chain Multiplication), it fails. However, for a special class of problems, making the locally optimal choice at each step is proven to lead to the globally optimal solution. The art of using greedy algorithms lies in identifying these problems and proving that the greedy strategy works.

To get a feel for this distinction, let's watch a short introduction.

The main takeaway is that a greedy algorithm bets on a specific heuristic. Our job is to find the right heuristic for the problem at hand. Let's see this in action with our first problem.

2. Activity Selection Problem

This is a classic problem that demonstrates the power of a correct greedy choice.

Problem Statement

You are given n activities, each with a start time and a finish time. You need to select the maximum number of activities that can be performed by a single person, knowing that a person can only work on one activity at a time.

Finding the Greedy Strategy

How should we greedily pick an activity? Let's consider a few options:

1. Earliest Start Time: Pick the activity that starts first. This seems intuitive, but what if that activity is very long and prevents many other shorter activities from being scheduled? This strategy can fail.
2. Shortest Duration: Pick the activity with the smallest duration (finish - start). This also seems plausible, as it occupies our schedule for the least amount of time. However, a short activity might be scheduled at a time that conflicts with two other activities that could have been scheduled back-to-back.
3. Earliest Finish Time: Pick the activity that finishes first. This is the winning strategy. By choosing an activity that finishes as early as possible, we free up our resource (the person) sooner, thus maximizing the remaining time for other activities.

The following video segment discusses these intuitive but incorrect strategies before arriving at the correct one.

The Algorithm and Proof of Correctness

The algorithm is straightforward:

1. Sort the activities based on their finish times in ascending order.
2. Select the first activity in the sorted list (since it's guaranteed to finish earliest).
3. Iterate through the remaining activities. For each activity, if its start time is greater than or equal to the finish time of the last selected activity, select it.

But why does this guarantee an optimal solution? The video provides a brief but powerful proof by exchange argument, which is a common way to validate greedy algorithms.

Java Implementation

Let's look at how to implement this in Java. Since you're aiming for interviews, being comfortable with custom sorting using Comparator is essential.

3. Fractional Knapsack Problem

Let's move to our second problem. This one highlights a key difference from a similar DP problem you'll encounter.

Problem Statement

You are given n items, each with a value and a weight. You have a knapsack with a maximum weight capacity W. You want to fill the knapsack with items to maximize the total value. The key detail is that you can take fractions of items.

This "fractional" property is what distinguishes it from the 0/1 Knapsack problem (where you must take an item whole or leave it), which requires Dynamic Programming.

Finding the Greedy Strategy

Again, we need a heuristic.

1. Highest Value: Pick the most valuable items first? This might fail if the most valuable item is also extremely heavy, filling our knapsack for little "efficiency".
2. Lightest Weight: Pick the lightest items first? This might fill our knapsack with items that are not very valuable.
3. Highest Value-to-Weight Ratio: For each item, calculate its "density" (value / weight). Pick items with the highest density first. This is the winning strategy, as it ensures that for every unit of weight we add to our knapsack, we are getting the maximum possible value.

The following segments demonstrate why the other strategies fail and why the value/weight ratio is the correct greedy choice.

Algorithm and Implementation

The algorithm follows directly from our greedy choice:

1. For each item, calculate its value-to-weight ratio (v/w).
2. Sort the items in descending order based on this ratio.
3. Iterate through the sorted items and add them to the knapsack.
   • If the entire item fits, take it all. Update the total value and remaining capacity.
   • If the entire item does not fit, take a fraction of it that fills the remaining capacity exactly. Add the value of this fraction to the total and stop.

For a detailed step-by-step walkthrough, implementation details, and Java code, the following article is an excellent resource.

The video from 'take U forward' also provides a solid walkthrough of the implementation logic and how to write the custom comparator, which you can use to supplement your reading.

Conclusion

Today you've learned the fundamentals of the greedy algorithmic paradigm and applied it to two classic problems. Unlike DP, which can feel like a brute-force search, greedy algorithms require you to find a clever, provably correct heuristic.

Key Takeaways:

• Greedy Algorithm: An approach that makes the locally optimal choice at each step, hoping to find a global optimum.
• When It Works: It works only for problems with the greedy choice property (a local optimum is part of a global optimum) and optimal substructure.
• Activity Selection: The greedy strategy is to sort activities by their finish times and pick the next compatible one.
• Fractional Knapsack: The greedy strategy is to sort items by their value-to-weight ratio and take as much as you can of the highest-ratio items.
• Implementation: The key technical skill in both problems is often custom sorting, which you can do efficiently in Java using Comparators or Comparable interfaces.

Preview of the Next Lesson:
In our next lesson, we will tackle problems involving merging overlapping intervals. This is a very common interview pattern that builds directly on the skills you practiced today, particularly sorting collections of objects based on a specific property to simplify a problem.