最大化游戏试玩资格分发2026 华为OD机试真题 4月26日华为OD上机新系统考试真题 100 分题型点击查看华为 OD 机试真题完整目录2026最新华为OD机试新系统卷 双机位C卷 真题题库目录全覆盖题库 逐点算法考点详解题目描述新研发了一台游戏设备可以面向用户接受试玩。现有n个试玩申请每个试玩有开始时间和结束时间。作为协调员为了能让更多人体验到游戏你需要对试玩申请进行选择使得任意两个被选中的试玩时间不重叠。任意两个被选中的试玩时间允许连续例如[2,3]和[3,4]认为是可以都被安排的。被安排的试玩数量最大化。请问最多能安排多少场试玩2026 华为OD机试真题 4月26日华为OD上机新系统考试真题 100 分题型输入描述第一行一个整数n($1 \le n \le 10^5$)表示试玩申请数量。第二行是一个长度为n的数组数组的每个元素为两个整数start和end($0 \le start \le end \le 10^9$)表示试玩的开始和结束时间。数组每个元素以空格分割元素内部中start和end使用逗号分割。输出描述一个整数表示最多能安排的试玩数量。示例1输入3 1,5 2,3 4,6输出2说明选择[2,3]和[4,6],共2位示例2输入5 1,2 3,4 5,6 7,8 9,10输出5说明5个试玩申请时间都不重合可同时满足示例3输入1 1,5输出1说明只有一个试玩请求可以直接安排。示例4输入3 1,5 2,4 3,6输出1说明所有试玩时间相互都冲突只能安排一场。解题思路本题是一个经典的区间调度问题Activity Selection Problem通常使用贪心算法求解。 目标是从给定的 $n$ 个区间中选出尽可能多的互不重叠的区间。核心思想为了能够安排更多的试玩我们需要优先安排那些结束时间早的试玩这样能为后面的试玩留出更多的时间。 具体步骤如下 1.排序将所有的试玩申请按照结束时间从小到大进行排序。如果结束时间相同按开始时间排序也可。 2.贪心选择维护一个当前已安排试玩的结束时间current_end初始值为 -1。遍历排序后的申请 - 如果当前试玩的开始时间$\ge$current_end说明它与之前安排的试玩不冲突题目允许连续时间例如[2,3]和[3,4]可以同时安排。 - 选择该试玩将安排的数量加一并更新current_end为当前试玩的结束时间。 3.返回结果遍历结束后所选择的试玩数量即为最大能安排的场次。复杂度分析-时间复杂度$O(n \log n)$主要耗时在对所有区间进行排序。贪心遍历只需要 $O(n)$。 -空间复杂度$O(1)$ 或 $O(n)$取决于语言内部排序算法的