PROBLEM SOLVING - GREEDY ALGORITHMS IN C

Greedy Basics in C

Greedy Definition

A greedy algorithm builds a solution by repeatedly choosing the best-looking option at the current step without undoing past choices.

Greedy-choice property — local optimum leads to global optimum
Optimal substructure — optimal solution contains optimal subsolutions
Typical pattern — sort, then scan with a greedy rule

// Activity selection sketch (sort by finish time)
for (i = 0; i < n; i++)
    if (activities[i].start >= last_finish)
        pick i, last_finish = activities[i].finish;

Greedy vs Dynamic Programming

Greedy	Dynamic Programming
One committed choice per step	Explores overlapping subproblems
Often O(n log n)	May be O(n²) or O(n·W)
Needs proof of correctness	Correct when recurrence holds
Example: fractional knapsack	Example: 0/1 knapsack