DSA Tutorial #17: Greedy Algorithms — Make the Best Choice at Every Step

Greedy algorithms make the locally optimal choice at each step, hoping it leads to a globally optimal solution. They are simpler than dynamic programming and often faster. But they only work when the greedy choice is provably correct. In this article, you will learn when greedy works, classic greedy problems, and how to tell greedy apart from DP.

We show core examples in Kotlin, Python, and Go.

What is a Greedy Algorithm?

A greedy algorithm makes the best possible choice at each step without looking ahead. It never reconsiders previous choices.

Simple example: making change with the fewest coins. If you have coins of 25, 10, 5, and 1, and you need to make 41 cents:

• Take a 25 (remaining: 16)
• Take a 10 (remaining: 6)
• Take a 5 (remaining: 1)
• Take a 1 (remaining: 0)
• Total: 4 coins

This greedy approach works for US coins. But it does NOT work for all coin systems. If coins are [1, 3, 4] and target is 6, greedy picks 4+1+1=3 coins, but the optimal is 3+3=2 coins. That is why coin change uses DP in the general case.

Greedy vs Dynamic Programming

How to tell: if making the locally best choice at each step always leads to the globally best solution, use greedy. If you need to consider multiple options and compare, use DP.

Interval Scheduling

Interval problems are the most classic greedy problems.

Activity Selection (Maximum Non-Overlapping Intervals)

Given a list of intervals with start and end times, find the maximum number of non-overlapping intervals.

Greedy strategy: Always pick the interval that ends earliest. This leaves the most room for future intervals.

Python:

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])  # Sort by end time
    count = 0
    last_end = float("-inf")
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Kotlin:

fun maxNonOverlapping(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[1] }
    var count = 0
    var lastEnd = Int.MIN_VALUE
    for ((start, end) in intervals) {
        if (start >= lastEnd) {
            count++
            lastEnd = end
        }
    }
    return count
}

Go:

import "sort"

func maxNonOverlapping(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    count := 0
    lastEnd := -1 << 63
    for _, interval := range intervals {
        if interval[0] >= lastEnd {
            count++
            lastEnd = interval[1]
        }
    }
    return count
}

Time: O(n log n) for sorting. Space: O(1).

Minimum Number of Meeting Rooms (Meeting Rooms II)

Given meeting intervals, find the minimum number of rooms needed.

Python:

import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])  # Sort by start time
    rooms = []  # Min-heap of end times
    heapq.heappush(rooms, intervals[0][1])
    for start, end in intervals[1:]:
        if start >= rooms[0]:
            heapq.heappop(rooms)  # Reuse the room
        heapq.heappush(rooms, end)
    return len(rooms)

Time: O(n log n). Space: O(n).

Merge Intervals

Sort by start time, then merge overlapping intervals.

Python:

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    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

Given an array where each element is the maximum jump length from that position, determine if you can reach the last index.

Greedy strategy: Track the farthest position you can reach. If you can reach or pass the last index, return true.

Python:

def can_jump(nums):
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False  # Cannot reach this position
        farthest = max(farthest, i + nums[i])
    return True

Kotlin:

fun canJump(nums: IntArray): Boolean {
    var farthest = 0
    for (i in nums.indices) {
        if (i > farthest) return false
        farthest = maxOf(farthest, i + nums[i])
    }
    return true
}

Go:

func canJump(nums []int) bool {
    farthest := 0
    for i := range nums {
        if i > farthest {
            return false
        }
        if i+nums[i] > farthest {
            farthest = i + nums[i]
        }
    }
    return true
}

Time: O(n). Space: O(1).

Jump Game II (Minimum Jumps)

Find the minimum number of jumps to reach the last index.

Python:

def jump(nums):
    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

Time: O(n). Space: O(1).

Assign Cookies

You have children with greed factors and cookies with sizes. Each child gets at most one cookie, and a child is satisfied only if cookie size >= greed factor. Maximize the number of satisfied children.

Greedy strategy: Sort both arrays. Give the smallest sufficient cookie to the least greedy child.

Python:

def find_content_children(children, cookies):
    children.sort()
    cookies.sort()
    child = cookie = 0
    while child < len(children) and cookie < len(cookies):
        if cookies[cookie] >= children[child]:
            child += 1
        cookie += 1
    return child

Time: O(n log n + m log m). Space: O(1).

Task Scheduler

Given tasks with cooldown period n between same tasks, find the minimum time to execute all tasks.

Greedy strategy: The most frequent task determines the minimum time. Fill gaps with other tasks.

Python:

from collections import Counter

def least_interval(tasks, n):
    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
    result = (max_freq - 1) * (n + 1) + max_count
    return max(result, len(tasks))

Kotlin:

fun leastInterval(tasks: CharArray, n: Int): Int {
    val freq = IntArray(26)
    for (task in tasks) freq[task - 'A']++
    val maxFreq = freq.max()
    val maxCount = freq.count { it == maxFreq }
    val result = (maxFreq - 1) * (n + 1) + maxCount
    return maxOf(result, tasks.size)
}

Time: O(n). Space: O(1) (fixed 26 letters).

Fractional Knapsack

You have items with weights and values, and a knapsack with capacity W. You can take fractions of items. Maximize total value.

Greedy strategy: Take items with the highest value-to-weight ratio first.

Python:

def fractional_knapsack(items, capacity):
    # items = [(value, weight), ...]
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    total_value = 0
    for value, weight in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break
    return total_value

Note: the 0/1 knapsack (cannot take fractions) requires DP. Greedy only works for fractional.

Huffman Coding (Simplified)

Huffman coding assigns shorter codes to more frequent characters. It uses a greedy approach:

1. Create a node for each character with its frequency
2. Repeatedly merge the two lowest-frequency nodes into a new node
3. The result is an optimal binary tree for encoding

This is greedy because at each step, we merge the two cheapest nodes. The proof uses the exchange argument: if you merge anything else, the total cost is equal or higher.

How to Prove Greedy Works

In interviews, you usually do not need a formal proof. But these strategies help convince yourself and the interviewer:

1. Exchange argument: Show that swapping the greedy choice for any other choice does not improve the solution
2. Stays ahead: Show that after each step, the greedy solution is at least as good as any other
3. Try counterexamples: If you cannot find a case where greedy fails, it probably works

Common Mistakes

1. Using greedy when DP is needed. If the greedy choice can lead to a suboptimal solution, use DP. Test with small examples.

2. Forgetting to sort. Most greedy algorithms require sorted input. Always check if sorting is needed.

3. Not handling ties correctly. When two choices have the same value, the tie-breaking rule matters.

4. Assuming greedy works without verification. Always test your greedy approach against a brute force solution on small inputs.

Practice Problems

What’s Next?

Now you know when to use greedy and when to use DP. The next article takes a deep dive into BFS and DFS patterns — Dijkstra’s algorithm, multi-source BFS, and grid-based graph problems that frequently appear in interviews.

Next: DSA Tutorial #18: BFS and DFS Deep Dive

Full series: DSA from Zero to Interview Ready