当前位置: 首页 > news >正文

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

题目描述

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

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

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

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

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

用例

输入2
720 120
840 120
输出1
说明两场演出间隔时间为0,不满足最小15分钟时间间隔的要求,所以最多只能观看一场演出
输入2
0 60
90 60
输出2
说明两场演出间隔大于15分钟,都能观看到

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

一、核心解题思路

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

  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 += 1last_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=150B: 200≥150+15=165 → 满足 → count=2, last_end=250C: 300≥250+15=265 → 满足 → count=3
结果:3
四、总结

算法优势

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

关键要点

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

适用场景

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

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

http://www.lryc.cn/news/583162.html

相关文章:

  • 七牛云C++开发面试题及参考答案
  • Vue 3 中父子组件双向绑定的 4 种方式
  • mysql互为主从失效,重新同步
  • qml加载html以及交互
  • HarmonyOS中各种动画的使用介绍
  • C语言extern的用法(非常详细,通俗易懂)
  • 〔从零搭建〕数据湖平台部署指南
  • 17.Spring Boot的Bean详解(新手版)
  • OpenCV颜色矩哈希算法------cv::img_hash::ColorMomentHash
  • STM32-待机唤醒实验
  • [Leetcode] 预处理 | 多叉树bfs | 格雷编码 | static_cast | 矩阵对角线
  • User手机上如何抓取界面的布局uiautomatorviewer
  • 【机器人】Aether 多任务世界模型 | 4D动态重建 | 视频预测 | 视觉规划
  • 速卖通跨境运营破局:亚矩阵云手机如何用“本地化黑科技”撬动俄罗斯市场25%客单价增长
  • React 编译器与性能优化:告别手动 Memoization
  • 开始读 PostgreSQL 16 Administration Cookbook
  • 苍穹外卖项目日记(day04)
  • 【Netty+WebSocket详解】WebSocket全双工通信与Netty的高效结合与实战
  • 冷冻电镜重构的GPU加速破局:从Relion到CryoSPARC的并行重构算法
  • 《重构项目》基于Apollo架构设计的项目重构方案(多种地图、多阶段、多任务、状态机管理)
  • 仓颉语言 1.0.0 升级指南:工具链适配、collection 操作重构与 Map 遍历删除避坑
  • IT系统安全刚需:绝缘故障定位系统
  • Tailwind CSS纵向滚动条设置
  • PiscTrace深蹲计数功能实现:基于 YOLO-Pose 和人体关键点分析
  • 基于Java+Maven+Testng+Selenium+Log4j+Allure+Jenkins搭建一个WebUI自动化框架(4)集成Allure报表
  • JavaScript数组方法——梳理和考点
  • SpringBoot实现动态Job实战
  • DRT-Net: Dual-Branch Rectangular Transformer with Contrastive Learning
  • 离线二维码生成器,无需网络快速制作
  • springBoot使用XWPFDocument 和 LoopRowTableRenderPolicy 两种方式填充数据到word模版中