def greedy_change(coins, amount):
    """
    贪心找零：使用面额从大到小排序的硬币凑成amount元
    :param coins: list[int] 硬币面额列表（不要求排序）
    :param amount: int 需要凑的金额
    :return: list[int] 选择的硬币列表
    """
    # 从大到小排序，确保先选最大面额
    coins.sort(reverse=True)  # 降序排列
    result = []               # 存储选中的硬币
    for coin in coins:
        # 能取多少个当前面额的硬币
        while amount >= coin:
            amount -= coin         # 减去已选的面额
            result.append(coin)   # 记录选择的硬币
    # 如果最后amount不为0，说明无法凑出（但本题假定硬币组合能凑出）
    if amount != 0:
        print("警告：无法用给定硬币凑出目标金额")
    return result

# 测试
coins = [10, 5, 2, 1]      # 人民币常用面额
money = 11                 # 需要找零11元
change = greedy_change(coins, money)
print("找零硬币：", change)   # 输出 [10, 1]
print("硬币数量：", len(change))  # 输出 2

# 活动选择：选最多不冲突的活动
def activity_selection(activities):
    """
    :param activities: list of (start, end) 每个活动用元组(开始, 结束)表示
    :return: list of int 选中的活动编号（按原始输入顺序）
    """
    # 按结束时间从小到大排序（关键！）
    # 同时保留每个活动原来的索引，方便后续输出
    indexed = [(i, start, end) for i, (start, end) in enumerate(activities)]
    indexed.sort(key=lambda x: x[2])  # 按结束时间排序

    selected = []            # 存放选中的活动编号
    last_end_time = 0        # 上一个选中活动的结束时间，初始为0

    for idx, start, end in indexed:
        # 如果当前活动的开始时间 >= 上一个活动的结束时间，则不冲突
        if start >= last_end_time:
            selected.append(idx)      # 选中这个活动
            last_end_time = end       # 更新结束时间

    return selected

# 测试：一些活动
activities = [
    (9, 10),   # 活动0: 9点到10点
    (9, 11),   # 活动1: 9点到11点
    (10, 12),  # 活动2: 10点到12点
    (11, 12),  # 活动3: 11点到12点
]
chosen = activity_selection(activities)
print("选中的活动编号：", chosen)  # 输出 [0, 3]（先选活动0，然后活动3）
# 还可以改为打印活动内容
for idx in chosen:
    s, e = activities[idx]
    print(f"活动{idx}: {s}:00 - {e}:00")

# 完整示例：贪心算法两个经典应用

# ----- 1. 找零钱问题 -----
def greedy_change(coins, amount):
    # coins: 硬币面额列表（不需要排序）
    # amount: 需要凑的金额
    coins.sort(reverse=True)  # 降序排序
    result = []               # 记录选中的硬币
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    if amount != 0:
        print("注意：无法用给定硬币凑出目标金额")
    return result

# 测试找零钱
coins = [5, 2, 10, 1]         # 人民币常用面额，故意乱序
money = 11
change = greedy_change(coins, money)
print("找零问题：")
print("硬币面额：", sorted(coins, reverse=True))
print("目标金额：", money)
print("方案：", change)
print("数量：", len(change))
print()

# ----- 2. 活动选择问题 -----
def activity_selection(activities):
    # 给每个活动加原始索引
    indexed = [(i, s, e) for i, (s, e) in enumerate(activities)]
    indexed.sort(key=lambda x: x[2])  # 按结束时间升序
    selected = []
    last_end = 0
    for idx, start, end in indexed:
        if start >= last_end:
            selected.append(idx)
            last_end = end
    return selected

# 测试活动选择
activities = [
    ("画画", 9, 10),
    ("打球", 9, 11),
    ("看书", 10, 12),
    ("游泳", 11, 12),
]
# 提取时间和名称
time_list = [(s, e) for _, s, e in activities]
name_list = [n for n, _, _ in activities]
chosen_idx = activity_selection(time_list)
print("活动选择问题：")
print("可选活动：")
for i, (n, s, e) in enumerate(activities):
    print(f"  {i}: {n}  {s}:00-{e}:00")
print("贪心选择的活动：")
for idx in chosen_idx:
    n, s, e = activities[idx]
    print(f"  {n}  {s}:00-{e}:00")