# ===== CodeLab: algo-greedy =====
# 以下代码片段按文章出现顺序拼接, 共 6 段

# ----- 片段 1 (python) -----
def coin_change_greedy(amount, coins):
    coins = sorted(coins, reverse=True)   # 大面额在前
    count = 0
    for c in coins:
        if amount == 0:
            break
        count += amount // c    # 尽量多用这张面额
        amount %= c             # 剩余部分交给更小面额
    return count if amount == 0 else -1   # 凑不齐返回 -1

print(coin_change_greedy(36, [1, 5, 10, 25]))   # 3:25+10+1
print(coin_change_greedy(30, [1, 5, 10, 25]))   # 2:25+5

# ----- 片段 2 (python) -----
# 面额 [1, 3, 4],凑 6
# 贪心:4 + 1 + 1 = 3 枚;最优:3 + 3 = 2 枚
print(coin_change_greedy(6, [1, 3, 4]))   # 3,不是最优!
# 这种"任意面额"的找零问题,正确解法是动态规划

# ----- 片段 3 (python) -----
def interval_schedule(intervals):
    intervals.sort(key=lambda x: x[1])   # 按结束时间升序
    count = 0
    last_end = float('-inf')
    for s, e in intervals:
        if s >= last_end:      # 与上一场不冲突
            count += 1
            last_end = e
    return count

meetings = [(1, 3), (2, 5), (3, 6), (5, 7), (6, 8)]
print(interval_schedule(meetings))   # 3:(1,3)(3,6)(6,8)

# ----- 片段 4 (python) -----
def can_jump(nums):
    farthest = 0
    for i, n in enumerate(nums):
        if i > farthest:          # 当前位置已经够不着
            return False
        farthest = max(farthest, i + n)
    return True

print(can_jump([2, 3, 1, 1, 4]))   # True
print(can_jump([3, 2, 1, 0, 4]))   # False,卡在 0 上

# ----- 片段 5 (python) -----
def jump(nums):
    n = len(nums)
    if n <= 1:
        return 0
    jumps = 0
    cur_end = 0      # 当前这跳能到的边界
    farthest = 0     # 扫描中发现的全局最远
    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:      # 走到当前跳的边界
            jumps += 1
            cur_end = farthest
    return jumps

print(jump([2, 3, 1, 1, 4]))   # 2:先到 1 号位,再到终点

# ----- 片段 6 (python) -----
def find_content_children(g, s):
    g.sort()      # 孩子胃口升序
    s.sort()      # 饼干尺寸升序
    i = j = 0
    while i < len(g) and j < len(s):
        if s[j] >= g[i]:   # 这块饼干能喂饱当前孩子
            i += 1
        j += 1             # 不管喂没喂饱,饼干都用掉了
    return i

print(find_content_children([1, 2, 3], [1, 1]))   # 1
print(find_content_children([1, 2], [1, 2, 3]))   # 2