Greedy Algorithms

This lesson introduces the greedy problem-solving technique.

We'll cover the following

Greedy algorithms

Greedy is an algorithmic paradigm that builds up a solution piece by piece; this means it chooses the next piece that offers the most obvious and immediate benefit. A greedy algorithm, as the name implies, always makes the choice that seems to be the best at the time. It makes a locally-optimal choice in the hope that it will lead to a globally optimal solution.

The problems where the locally-optimal choice leads to a global solution are the best fit for the Greedy technique.

The greedy method can optimally solve a problem that satisfies the below-mentioned properties:

  1. Greedy choice property: A global optimum can be arrived at by selecting a local optimum.
  2. Optimal substructure: An optimal solution to the problem contains an optimal solution to subproblems.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.