Greedy Algorithms

When to Use

• Problem asks for min/max and locally optimal choice leads to globally optimal result
• No need to revisit past choices (contrast: DP considers all options)
• Sort first, then scan linearly with a simple decision rule at each step

Signal phrases: "minimum number of X", "maximum non-overlapping", "greedy", "can always", "schedule", "jump", "minimum jumps", "candy"

Greedy vs DP: If subproblems overlap and past choices constrain future ones → DP. If local choice never invalidates future choices (provable via exchange argument) → Greedy.

---

Pattern 1 — Activity Selection (Sort by End)

Maximize non-overlapping intervals. Always pick the interval that ends earliest — leaves maximum room for future intervals.

# LC 435 — Non-Overlapping Intervals (min removals to make non-overlapping)
def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])   # sort by END
    count = 0
    last_end = float('-inf')

    for start, end in intervals:
        if start >= last_end:
            last_end = end   # keep — no overlap
        else:
            count += 1       # remove — overlaps with last kept

    return count

Why sort by end? Greedily keeping the earliest-ending interval leaves maximum room. Proof by exchange: if you swap in a later-ending interval, you can only do worse or equal.

---

Pattern 2 — Jump Game (Track Furthest Reachable)

Don't simulate jumps. Track the furthest index reachable at each step.

# LC 55 — Jump Game I (feasibility)
def canJump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False                    # stuck — can't reach i
        max_reach = max(max_reach, i + jump)
    return True

# LC 45 — Jump Game II (minimum jumps)
def jump(nums):
    jumps = 0
    current_end = 0    # boundary of current jump
    farthest = 0       # farthest we can reach with one more jump

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:    # exhausted current jump range → must jump
            jumps += 1
            current_end = farthest
            if current_end >= len(nums) - 1:
                break

    return jumps

---

Pattern 3 — Two-Pass Greedy (Propagate Bidirectional Constraints)

When each element depends on both left and right neighbors, two passes are needed.

# LC 135 — Candy
def candy(ratings):
    n = len(ratings)
    candy = [1] * n

    # Left pass: right neighbor with higher rating gets one more than left
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candy[i] = candy[i-1] + 1

    # Right pass: left neighbor with higher rating must beat right side too
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candy[i] = max(candy[i], candy[i+1] + 1)   # take max — satisfy both

    return sum(candy)

Key insight: Left pass satisfies rating[i] > rating[i-1]. Right pass satisfies rating[i] > rating[i+1]. max combines both — you need to satisfy whichever constraint is stricter.

---

Pattern 4 — Gas Station (Circular Greedy)

If total gas >= total cost, a solution exists. Start where running sum first went negative.

# LC 134 — Gas Station
def canCompleteCircuit(gas, cost):
    total = 0
    tank = 0
    start = 0

    for i in range(len(gas)):
        total += gas[i] - cost[i]
        tank += gas[i] - cost[i]
        if tank < 0:       # can't start from here or earlier
            start = i + 1  # try next station
            tank = 0

    return start if total >= 0 else -1

Key insight: If total balance >= 0, exactly one valid starting point exists. The greedy reset (start = i+1) finds it in one pass.

---

Pattern 5 — Greedy with Priority Queue

When the greedy choice requires knowing current max/min efficiently.

# LC 621 — Task Scheduler
from collections import Counter
import heapq
from collections import deque

def leastInterval(tasks, n):
    count = Counter(tasks)
    max_heap = [-c for c in count.values()]
    heapq.heapify(max_heap)

    time = 0
    cooldown_queue = deque()   # (remaining_count, available_at_time)

    while max_heap or cooldown_queue:
        time += 1
        if max_heap:
            cnt = 1 + heapq.heappop(max_heap)    # process one
            if cnt:                               # still has tasks left
                cooldown_queue.append((cnt, time + n))
        if cooldown_queue and cooldown_queue[0][1] == time:
            heapq.heappush(max_heap, cooldown_queue.popleft()[0])

    return time

---

Pattern 6 — Partition Labels (Last Occurrence Greedy)

Extend each partition to the last occurrence of every character in it.

# LC 763 — Partition Labels
def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}   # last occurrence of each char
    result = []
    start = end = 0

    for i, c in enumerate(s):
        end = max(end, last[c])    # extend partition to cover this char's last occurrence
        if i == end:               # we've processed all chars that must be in this partition
            result.append(end - start + 1)
            start = i + 1

    return result

---

Pattern 7 — Optimal Merge / Connect Ropes (Min-Heap)

Combine items pairwise where cost = sum of sizes. Minimize total cost by always merging two smallest.

import heapq

# GFG — Connect Ropes with Minimum Cost
def connectRopes(ropes):
    heapq.heapify(ropes)        # O(N) build heap
    total_cost = 0
    while len(ropes) > 1:
        first = heapq.heappop(ropes)
        second = heapq.heappop(ropes)
        cost = first + second
        total_cost += cost
        heapq.heappush(ropes, cost)
    return total_cost

Why merge smallest first? Large values propagate through more merges (deeper in merge tree). Keeping them small as long as possible minimizes their contribution. Same logic as Huffman coding.

Signals: "minimum cost to connect/merge all", "combine ropes/files/stones", cost = sum of two sizes.

---

Pattern 8 — Fractional Knapsack (Sort by Value/Weight Ratio)

Unlike 0/1 Knapsack (DP), items are divisible — take fractions. Sort by ratio desc, greedily fill.

def fractionalKnapsack(items, capacity):
    # items = [(value, weight), ...]
    items.sort(key=lambda x: x[0] / x[1], reverse=True)   # sort by ratio desc
    total_value = 0.0
    for value, weight in items:
        if capacity >= weight:
            total_value += value        # take whole item
            capacity -= weight
        else:
            total_value += value * (capacity / weight)   # take fraction
            break                        # knapsack full
    return total_value

Signals: "fraction allowed", "items divisible", "gold dust/liquid", Value + Weight given. If items NOT divisible → 0/1 Knapsack (DP).

---

Pattern 9 — Two-Pointer Pairing / Partitioning

Sort both arrays. Match heaviest with lightest to satisfy constraints with fewest resources.

# LC 881 — Boats to Save People
def numRescueBoats(people, limit):
    people.sort()
    left, right = 0, len(people) - 1
    boats = 0
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1       # lightest fits with heaviest
        right -= 1          # heaviest always gets a boat
        boats += 1
    return boats

# LC 455 — Assign Cookies (smallest cookie that satisfies child)
def findContentChildren(greed, sizes):
    greed.sort()
    sizes.sort()
    child = cookie = 0
    while child < len(greed) and cookie < len(sizes):
        if sizes[cookie] >= greed[child]:
            child += 1      # satisfied
        cookie += 1
    return child

Signals: "matching two arrays", "boats/cookies/pairs", "one unit holds at most 2", capacity constraints.

---

Pattern 10 — Job Sequencing with Deadlines

Maximize profit when each job takes 1 unit time and has a deadline. Schedule jobs as late as possible.

def jobSequencing(jobs, max_deadline):
    # jobs = [(profit, deadline), ...]
    jobs.sort(key=lambda x: -x[0])          # sort by profit desc (greedy: high profit first)
    slots = [False] * (max_deadline + 1)
    total_profit = 0
    for profit, deadline in jobs:
        for t in range(min(max_deadline, deadline), 0, -1):   # find latest free slot
            if not slots[t]:
                slots[t] = True
                total_profit += profit
                break
    return total_profit

Why schedule as late as possible? Keeps early slots open for jobs with earlier deadlines. Proof by exchange: swapping a less-profitable job with a more-profitable one never decreases profit.

Signals: "profit", "deadline", "each job takes 1 unit", maximize total profit.

---

Pattern 11 — Interval Partitioning (Min Rooms / Platforms)

Find minimum resources (rooms, platforms) to handle all intervals without conflict.

import heapq

# LC 253 — Meeting Rooms II
def minMeetingRooms(intervals):
    intervals.sort(key=lambda x: x[0])   # sort by start time
    heap = []    # min-heap of end times (active rooms)
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse room (release + reassign)
        else:
            heapq.heappush(heap, end)     # need new room
    return len(heap)

Key insight: Heap tracks currently occupied rooms by end time. If earliest-ending room finishes before current start → reuse it. Heap size = rooms needed at peak.

Signals: "minimum rooms/platforms/resources", overlapping intervals, resource reuse after finish.

---

Pattern 12 — Deadlines + Durations (Max Tasks, Drop Longest)

Each task has duration and deadline. Sort by deadline; keep max-heap of durations. If over budget, drop longest task.

import heapq

# LC 630 — Course Schedule III
def scheduleCourse(courses):
    courses.sort(key=lambda x: x[1])   # sort by deadline (last day)
    heap = []   # max-heap of durations (negate for Python min-heap)
    time = 0
    for duration, deadline in courses:
        time += duration
        heapq.heappush(heap, -duration)
        if time > deadline:             # over budget — drop longest
            time += heapq.heappop(heap)  # heappop returns -duration (negative)
    return len(heap)

Key insight: Dropping the longest course frees the most time without reducing count — exchange argument proves this optimal.

---

Pattern 13 — Greedy + Monotonic Stack (Remove K Digits)

Remove k digits to form lexicographically smallest number. Pop larger stack tops when current digit is smaller.

# LC 402 — Remove K Digits
def removeKdigits(num, k):
    stack = []
    for c in num:
        while k > 0 and stack and stack[-1] > c:
            stack.pop()
            k -= 1
        if not (stack == [] and c == '0'):   # avoid leading zeros
            stack.append(c)
    while k > 0 and stack:       # remove from end if k remaining
        stack.pop()
        k -= 1
    return ''.join(stack) if stack else '0'

---

Pattern Recognition — How to Choose

---

When Greedy Fails (Use DP/Backtracking)

• 0/1 Knapsack — items not divisible; greedy by ratio fails (classic counterexample)
• Weighted Interval Scheduling — greedy by finish time ignores weights; need DP
• Coin Change (non-canonical) — for arbitrary denominations like {1,3,4}, greedy may overshoot
• Traveling Salesman — nearest neighbor (greedy) not globally optimal

Test before committing: Try to craft a 4–6 element counterexample. If none exists and it matches a known pattern → greedy is likely correct.

---

Problems

---

Complexity

• Usually O(N log N) if sort needed, O(N) if not
• No backtracking → no exponential blowup
• Space: O(1) extra or O(N) for heap/queue

---

Related

• [[DSA/DSA Techniques for Interviews/14. Merge Intervals]] — interval greedy problems
• [[DSA/DSA Techniques for Interviews/09. Heap & Priority Queue]] — greedy + heap combos
• [[DSA/DSA Techniques for Interviews/12. Dynamic Programming]] — when greedy is tempting but wrong