# Defining Greedy Algorithm

An algorithm is called *greedy* if it follows the problem-solving heuristic of making the *locally* optimal choice at each stage with the aim of finding a *global* optimum.

In most situations, a greedy strategy does not lead to the optimal solution. Hence, it is extremely important to reason about the correctness of the greedy strategy before using it to solve a problem.

## Problem 1: Too much to do!

Let's say you have to maximise the number of tasks that you complete in a 10-hour duration. You are given an array T = [2, 4, 1, 6] where T_{i} denotes the time required to complete the i^{th} task.

The answer to this question would be **3** as you would choose to do tasks** T _{2}, T_{0}** and

**T**— which take 1, 2 and 4 hours respectively to complete, for a total of 7 hours. Although we can easily calculate the answer in this small case, let's see what our strategy would be in if there were many more tasks.

_{1 }The greedy strategy for this problem is fairly straightforward. We always want to do the task with **minimum duration first**.

At each moment when you are required to make a decision, the optimal strategy would be to choose one of the remaining tasks which takes the **minimum time**. Here, our *locally* optimal choice is choosing the task with minimum time and we reach the *global* optimum by repeatedly doing this.

The following code carries out the greedy approach.

type=c odeblock|id=min_greedy|autocreate=cppint n = 7, hours = 50;int T[7] = {10, 100, 4, 16, 8, 17, 28};int sum = 0, i = 0;sort(T, T+n);for (i = 0; i < n; i++) {if (sum + T[i] > hours) break;sum = sum + T[i];}cout << "Maximum number of tasks that can be done in " << hours << " hours is: " << i << endl;