Greedy

Greedy#

A greedy algorithm makes the locally optimal choice at each step. Correct when the problem has the greedy choice property and optimal substructure; otherwise it produces a fast wrong answer. Always prove correctness before relying on greedy.

Interval scheduling#

Pick the maximum number of non-overlapping intervals.

def schedule(intervals):
    """Each interval is (start, end). Greedy by earliest end."""
    picked = []
    for start, end in sorted(intervals, key=lambda iv: iv[1]):
        if not picked or start >= picked[-1][1]:
            picked.append((start, end))
    return picked

Token bucket (rate limiting)#

A greedy admit-now-if-tokens-available algorithm.

import time

class TokenBucket:
    def __init__(self, rate: float, burst: int):
        self.rate = rate         # tokens per second
        self.burst = burst       # max tokens
        self.tokens = burst
        self.last = time.monotonic()

    def admit(self, cost: float = 1) -> bool:
        now = time.monotonic()
        self.tokens = min(self.burst,
                          self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

bucket = TokenBucket(rate=10, burst=20)   # 10 req/s, burst 20
if bucket.admit():
    send(request)

References#

Contents