Greedy Algorithms

Make the locally optimal choice at each step, sometimes that's globally optimal

A greedy algorithm makes the locally optimal choice at each step, hoping it leads to a globally optimal solution. Unlike DP, it doesn't reconsider past choices.
Greedy works when: the problem has the *greedy choice property*, local optimal choices lead to a global optimum.
Classic greedy problems: interval scheduling, Huffman encoding, Dijkstra's algorithm, fractional knapsack.

Interval scheduling, maximize non-overlapping intervalspython

def max_non_overlapping(intervals):
    """Select maximum number of non-overlapping intervals."""
    # Greedy: always pick the interval that ends earliest
    intervals.sort(key=lambda x: x[1])  # Sort by end time

    count = 1
    last_end = intervals[0][1]

    for start, end in intervals[1:]:
        if start >= last_end:  # No overlap
            count += 1
            last_end = end

    return count

intervals = [(1,3),(2,4),(3,5),(6,8)]
print(max_non_overlapping(intervals))  # → 3 ([1,3],[3,5],[6,8])

🤔Quick Check

Why does sorting by end time work for interval scheduling?

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Jump Game

Each element represents max jump length from that position. Can you reach the last index?
Expected output: True

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next