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.

Iteration Value picked Current time Jobs done
1st 0 0
2nd 1 0+1 = 1 1
3rd 2 1 + 2 = 3 2
4th 3 3 + 3 = 6 3

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.

You may also like...