A Greedy algorithm is an algorithmic approach that makes the locally optimal choice at each step with the hope of finding a global optimum. In other words, it makes the best decision at each step by choosing the most beneficial option available at that moment, without considering the long-term effects of that decision.
Greedy algorithms are used to solve optimization problems, where the goal is to find the best solution from a set of possible solutions. They work by iteratively making a series of choices that maximize (or minimize) some measure of performance or cost.
One of the key advantages of Greedy algorithms is their simplicity and speed. They can often provide a good approximation to the optimal solution in a relatively short amount of time. However, they do not always guarantee an optimal solution and may only provide an approximate solution that is close to the optimal one.
Some common examples of problems that can be solved using Greedy algorithms include the Activity Selection Problem, Knapsack problem, the Minimum Spanning Tree problem, and the Huffman coding problem.
We can take an example of Activity Selection Problem to understand the greedy approach. This problem is also important for interviews, and it has been asked many times in different interviews:
The Activity Selection Problem is an optimization problem in which you are given a set of activities, each with a start and finish time. The goal is to select the maximum number of activities that can be performed by a single person or resource, assuming that a person can only work on a single activity at a time.
A common approach to solving the Activity Selection Problem is to use a Greedy algorithm. The idea is to sort the activities by their finish times and always select the next activity that finishes first. This ensures that there is always enough time to perform the maximum number of activities.
Here’s an example: Suppose you have the following activities with their start and finish times: (1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14). The optimal solution to this problem would be to select activities (1, 4), (5, 7), (8, 11), and (12, 14) for a total of four activities.
The above code is an implementation of the Greedy algorithm for solving the Activity Selection Problem. The PrintMaxActivities function takes as input two arrays s and f of length n, representing the start and finish times of n activities, respectively. The goal is to select the maximum number of activities that can be performed by a single person or resource, assuming that a person can only work on a single activity at a time.
The function starts by initializing a variable i to 0, representing the index of the first activity to be selected. It then prints the index of this activity to the console using Console.Write(i + " ").
Next, the function enters a loop that iterates over the remaining activities from index 1 to n-1. For each activity j, it checks if the start time s[j] is greater than or equal to the finish time f[i] of the previously selected activity. If this condition is true, it means that the activity j can be performed after the activity i, so it prints the index of activity j to the console using Console.Write(j + " ") and updates the value of i to j.
By the end of the loop, the function will have printed the indices of all activities that can be performed by a single person or resource without overlapping.
public void PrintMaxActivities(int[] s, int[] f, int n)
{
int i = 0;
Console.Write(i + " ");
for (int j = 1; j < n; j++)
{
if (s[j] >= f[i])
{
Console.Write(j + " ");
i = j;
}
}
}
Time Complexity: O(N)
Auxiliary Space: O(1)