Portfolio/Learn/Greedy Algorithms: When Local Optimum = Global Optimum
Algorithms & DSIntermediate

Greedy Algorithms: When Local Optimum = Global Optimum

Learn when and why greedy works — interval scheduling, activity selection, Huffman coding, and the proof techniques that validate greedy choices.

14 min read
March 7, 2026
GreedyIntervalsSchedulingOptimizationPython

When Does Greedy Work?

Greedy algorithms make the locally optimal choice at each step, hoping it leads to a globally optimal solution. This works when the problem has the greedy-choice property (a local optimum is part of a global optimum) and optimal substructure. The hardest part is recognizing when greedy applies and proving correctness.

Greedy vs DP: if making the best local choice always leads to the global optimum, use greedy (faster, simpler). If you need to consider multiple choices and their consequences, use DP. When in doubt, try greedy first — if you can construct a counterexample, switch to DP.

Interval Scheduling

Given intervals, find the maximum number of non-overlapping intervals. The greedy strategy: sort by end time, always pick the interval that ends earliest. This leaves the most room for future intervals.

python
def max_non_overlapping(intervals: list[list[int]]) -> int:
    """Maximum number of non-overlapping intervals."""
    intervals.sort(key=lambda x: x[1])  # Sort by end time
    count = 0
    prev_end = float("-inf")

    for start, end in intervals:
        if start >= prev_end:
            count += 1
            prev_end = end

    return count


def min_intervals_to_remove(intervals: list[list[int]]) -> int:
    """Minimum removals to make all intervals non-overlapping."""
    return len(intervals) - max_non_overlapping(intervals)

Merge Intervals

python
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    """Merge all overlapping intervals."""
    intervals.sort()
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

Jump Game

At each position, you can jump up to nums[i] steps. Can you reach the end? Greedy approach: track the farthest reachable position. If you ever can't advance past your current position, you're stuck.

python
def can_jump(nums: list[int]) -> bool:
    """Can you reach the last index?"""
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])
    return True


def min_jumps(nums: list[int]) -> int:
    """Minimum jumps to reach the end."""
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

Task Scheduling

python
def task_scheduler(tasks: list[str], n: int) -> int:
    """Minimum intervals to execute all tasks with cooldown n."""
    from collections import Counter
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for f in freq.values() if f == max_freq)

    # Formula: (max_freq - 1) * (n + 1) + max_count
    # But result can't be less than total tasks
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

Common greedy problems: interval scheduling, activity selection, Huffman coding, fractional knapsack, gas station, candy distribution, and jump game variants. For each, identify what to sort by and what greedy choice to make.

More Articles