Algorithm Techniques – Greedy

A greedy algorithm is always making the choice that seems to be the best at that moment.

In other words, this means that a locally-optimal choice is made, which will hopefully lead to a globally-optimal solution.

A greedy algorithm has only one shot to compute the optimal solution, so one characteristic is that it never goes back to reverses the decision.

Creation of a greedy algorithm:

Problem: You have a T time to do the work, and you are required to do the maximum number of jobs.

So, how would you make the maximum number of jobs in a given time? By doing only the smallest task possible, for as much as possible.

Input:

• An array A of integers, where each element indicates the time it takes to complete the job
• Time T, which indicates the time required to do things

Data to use:

• A variable to indicate the current time
• A variable to indicate the number of jobs done

Operations to perform:

• Sort the array (increasing order)
• Take each item one by one
• Increment current time to the time took to complete the item
• Increment with 1 the number of jobs successfully done

Repeat this as long as current time is smaller or equal to T (final time).

Example:

Input:

• A = {3, 5, 2, 1, 4}
• T = 5

Preparation: Sort the array.

After the 4th iteration, current time (6) is bigger than our max time T (4). Thus, the maximum number of jobs that can be performed in such time is 3.