华为OD机试_2025 B卷_观看文艺汇演问题（Python，100分）（附详细解题思路）

题目描述

为了庆祝中国共产党成立100周年，某公园将举行多场文艺表演，很多演出都是同时进行，一个人只能同时观看一场演出，且不能迟到早退，由于演出分布在不同的演出场地，所以连续观看的演出最少有15分钟的时间间隔，

小明是一个狂热的文艺迷，想观看尽可能多的演出， 现给出演出时间表，请帮小明计算他最多能观看几场演出。

输入描述
第一行为一个数N，表示演出场数，1<=N<=1000，接下来N行，每行有被空格分割的两个整数，

第一个整数T表示演出的开始时间，第二个整数L表示演出的持续时间，T和L的单位为分钟，0<=T<=1440,0<L<=100.

输出描述
输出最多能观看的演出场数。

用例

最大观看演出场数问题详解

一、核心解题思路

问题分析
题目要求计算在满足观看规则的前提下，小明最多能观看多少场演出：

1. 不能同时观看两场演出（演出时间不能重叠）
2. 连续观看的演出之间至少需要15分钟间隔
3. 每场演出有固定的开始时间和持续时间

关键特性

1. 时间区间限制：每场演出可表示为 [T, T+L) 的时间区间
2. 间隔要求：相邻演出结束与开始时间至少间隔15分钟
3. 最大化目标：选择尽可能多的兼容区间

贪心算法策略

1. 按结束时间排序：优先选择结束时间早的演出，为后续观看留出更多时间
2. 兼容性检查：当前演出开始时间 ≥ 上一场结束时间 + 15分钟
3. 逐步选择：依次选择符合条件的演出，直到所有演出都被检查

算法流程

1. 计算每个演出的结束时间 = 开始时间 + 持续时间
2. 按结束时间对所有演出排序
3. 初始化：
   - 已观看场次 count = 0
   - 上一场结束时间 last_end = -∞
4. 遍历排序后的演出：
   if 当前演出开始时间 ≥ last_end + 15:
       更新 last_end = 当前演出结束时间
       count += 1
5. 返回 count

二、完整代码实现

def main():
    # 读取输入
    n = int(input().strip())
    performances = []
    
    # 解析每场演出的开始时间和持续时间
    for i in range(n):
        T, L = map(int, input().split())
        performances.append((T, T + L))  # (开始时间, 结束时间)
    
    # 按结束时间排序
    performances.sort(key=lambda x: x[1])
    
    count = 0  # 观看场次计数
    last_end = -10**9  # 初始化为极小值
    
    # 遍历排序后的演出
    for start, end in performances:
        if start >= last_end + 15:
            count += 1
            last_end = end
    
    # 输出结果
    print(count)

if __name__ == "__main__":
    main()

代码解析：

1. 输入处理：

   • 读取演出总场数n
   • 解析每场演出的开始时间T和持续时间L
   • 存储为元组(开始时间, 结束时间)

2. 关键排序：

   • 使用sort(key=lambda x: x)按结束时间升序排序
   • 贪心策略的基础：优先选择结束早的演出

3. 遍历选择：

   • 初始化last_end为极小值（确保第一场演出能被选择）
   • 检查条件：start >= last_end + 15
   • 更新计数和结束时间

4. 输出结果：

   • 打印满足条件的最大演出场数

三、示例解析

示例1：输入 2\n720 120\n840 120

演出数据：
  演出A: 开始=720, 结束=840
  演出B: 开始=840, 结束=960

排序后: [A(720,840), B(840,960)]
遍历过程：
  演出A: 开始720 ≥ -∞+15? → 满足 → count=1, last_end=840
  演出B: 开始840 ≥ 840+15? → 855>840 → 不满足
结果：1

示例2：输入 2\n0 60\n90 60

演出数据：
  演出A: 开始=0, 结束=60
  演出B: 开始=90, 结束=150

排序后: [A(0,60), B(90,150)]
遍历过程：
  演出A: 0 ≥ -∞+15 → 满足 → count=1, last_end=60
  演出B: 90 ≥ 60+15 → 90≥75 → 满足 → count=2
结果：2

复杂案例：输入 3\n100 50\n200 50\n300 50

演出数据：
  A: [100,150]
  B: [200,250]
  C: [300,350]
  
排序后: [A,B,C]
遍历：
  A: 满足 → count=1, last_end=150
  B: 200≥150+15=165 → 满足 → count=2, last_end=250
  C: 300≥250+15=265 → 满足 → count=3
结果：3

四、总结

算法优势：

1. 高效简单：时间复杂度O(n log n)，主要来自排序操作
2. 最优解保证：贪心策略能获得最大观看场次
3. 直观易懂：按结束时间排序符合现实逻辑

关键要点：

• 排序是核心：按结束时间排序确保最优选择
• 间隔条件处理：last_end+15 体现15分钟间隔要求
• 边界处理：初始化last_end为极小值确保第一场可选

适用场景：

• 区间调度问题（会议安排、课程选择等）
• 资源分配优化（共享资源的时间分配）
• 需要最大化兼容事件数量的场景

这种解法完全满足题目要求，通过贪心算法高效解决了带间隔约束的区间调度问题，代码简洁且性能优异。