Greedy

First PublishedFeb 11, 2026ByAtif Alam

Difficulty: High. ROI: Low.

Other common names: Greedy algorithm, myopic strategy.

When to use: Use when a series of locally best choices (by some criterion) is guaranteed to yield a global optimum — e.g. interval scheduling, Huffman coding, certain coin change or scheduling problems. Not every problem has a correct greedy; sometimes you need proof.

Idea: At each step, choose the option that looks best by a chosen rule (e.g. earliest finish time, smallest weight). Greedy is correct only when the problem has greedy choice property and optimal substructure.

Time / space: Often O(n log n) for sorting plus O(n) for a single pass. Space O(1) or O(n) depending on the algorithm.

Example #1 — Interval Scheduling

Choose the maximum number of non-overlapping intervals by sorting by end time and greedily taking each interval that starts at or after the end of the last chosen one.

Sample input and output

intervals = [(1, 3), (2, 4), (3, 5), (0, 6)]
print(max_intervals(intervals))  # 2  (e.g. (1,3) and (3,5))

• Sample input: intervals = [(1, 3), (2, 4), (3, 5), (0, 6)] (each pair is start, end).
• Sample output: 2 — we can take at most 2 non-overlapping intervals (e.g. (1,3) and (3,5)); the greedy picks (1,3) then (3,5).

Code (with inline comments)

# Interval scheduling: max number of non-overlapping intervals (by end time)
def max_intervals(intervals):
    intervals.sort(key=lambda x: x[1])  # sort by end time so we pick "earliest finish" first
    count = 0
    last_end = -float('inf')   # no interval chosen yet; -inf so first start is always >= this
    for start, end in intervals:
        if start >= last_end:  # this interval doesn't overlap the last chosen one
            count += 1
            last_end = end
    return count

Line-by-line:

• intervals.sort(key=lambda x: x[1]) — lambda x: x[1] is a small function that returns the second element of each interval (the end time). Sorting by end time lets us greedily pick the interval that finishes earliest among those that don’t overlap what we’ve already chosen.
• last_end = -float('inf') — float(‘inf’) is infinity; we use negative infinity so that the first interval’s start is always ≥ last_end (we can always take the first one).
• if start >= last_end: — The current interval starts at or after when the last chosen one ended, so they don’t overlap. We take it and update last_end to this interval’s end.

Execution trace (numbered list)

After sorting by end time: [(1,3), (2,4), (3,5), (0,6)]. last_end = -inf.

1. Step 1: (1,3), start 1 ≥ -inf → count=1, last_end=3.
2. Step 2: (2,4), start 2 < 3 → skip.
3. Step 3: (3,5), start 3 ≥ 3 → count=2, last_end=5.
4. Step 4: (0,6), start 0 < 5 → skip. Return 2.

Execution trace (code with step comments)

intervals = [(1,3), (2,4), (3,5), (0,6)]
intervals.sort(key=lambda x: x[1])  # [(1,3), (2,4), (3,5), (0,6)]
last_end = -float('inf')
# (1,3): 1 >= -inf → count=1, last_end=3
# (2,4): 2 < 3 → skip
# (3,5): 3 >= 3 → count=2, last_end=5
# (0,6): 0 < 5 → skip
# return 2

Execution trace (ASCII diagram)

Timeline; each interval is a segment. Greedy picks earliest-finish that doesn’t overlap.

Sorted by end: (1,3) (2,4) (3,5) (0,6)
Time:    0   1   2   3   4   5   6
         |-------| (1,3)  ✓ take
             |-------| (2,4)  skip (overlaps)
                 |-------| (3,5)  ✓ take
         |---------------| (0,6)  skip
Result: 2 intervals