Greedy Algorithms

def make_change(amount, coins):
    coins = sorted(coins, reverse=True)   # ใหญ่ไปเล็ก
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin            # เลือกเหรียญใหญ่สุดที่ใช้ได้
            result.append(coin)
    return result

print(make_change(63, [1, 5, 10, 20]))   # [20,20,20,1,1,1]

def max_activities(activities):
    # activities = [(start, end), ...]
    activities.sort(key=lambda a: a[1])   # เรียงตามเวลาจบ
    count, last_end = 0, 0
    for start, end in activities:
        if start >= last_end:             # ไม่ทับ
            count += 1
            last_end = end
    return count

print(max_activities([(1, 3), (2, 5), (4, 6), (6, 8)]))   # 3

# coins = [1, 3, 4], ทอน 6
# greedy: 4 + 1 + 1 = 3 เหรียญ  (ผิด!)
# คำตอบจริง: 3 + 3 = 2 เหรียญ  (DP หาเจอ)