2026 华为OD机试真题 4月26日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

新研发了一台游戏设备可以面向用户接受试玩。现有 n 个试玩申请，每个试玩有开始时间和结束时间。作为协调员，为了能让更多人体验到游戏，你需要对试玩申请进行选择，使得：

1. 任意两个被选中的试玩时间不重叠。

2. 任意两个被选中的试玩时间允许连续，例如 [2,3] 和 [3,4] 认为是可以都被安排的。

3. 被安排的试玩数量最大化。

请问最多能安排多少场试玩？

输入描述

第一行：一个整数 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)$，取决于语言内部排序算法的空间开销。