Greedy Algorithms

    DSA · Intermediate

    Definition

    A greedy algorithm makes the locally best choice at each step hoping to reach the global optimum.

    Greedy solutions are simple and fast for scheduling, intervals and coin problems.

    Diagram

    Meetings sorted by …pick earliest endskip overlapsmax meetings

    Flowchart

    Sort or prioritise optionsPick the best current choiceCheck it is validRepeatProve optimality

    Example: Max non-overlapping intervals

    iv = [(1,3),(2,4),(3,5),(6,7)]
iv.sort(key=lambda x: x[1])
end, count = -1, 0
for s, e in iv:
    if s >= end:
        count += 1; end = e
print(count)

    Output: 3

    Complexity

    Often O(n log n) due to sorting

    Key points

    • Not always correct
    • Needs greedy-choice property
    • Examples: Kruskal, Huffman, activity selection

    Interview questions

    When does greedy fail?

    Coin change with coins {1,3,4} for 6: greedy gives 4+1+1, optimal is 3+3.

    More DSA topics

    ArraysLinked ListStackQueue