**LLM推理批次最大化**
2026 华为OD机试真题8月12日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
大语言模型推理时，显存中有一个 KV Cache，用于存储各请求的键值对。现有 N 个推理请求排队，第 i 个请求需要占用 KV Cache 中一段连续位置 [Li,Ri]。每个位置同一时间只能分配给一个请求。请选出尽可能多的请求，使它们的区间互不重叠，从而最大化批次的吞吐量。
2026 华为OD机试真题8月12日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
输入描述
requests：由 N 个推理请求构成的二维数组，requests[i]表示第 i 个推理请求，其内容为[Li,Ri]。- 数组长度 N 满足
1 <= N <= 10^5。 - 每个位置
[Li,Ri]满足0 <= Li <= Ri <= 10^9。
输入为一行 JSON-like 二维数组，例如：
[[1,3],[2,5],[4,7]]输出描述
输出一个整数，表示最多可选多少个不重叠区间的请求。
注意：若两个区间端点相接，例如 [1,3] 和 [3,5]，由于位置 3 被共同占用，仍然认为重叠。
示例1
输入
[[1,3],[2,5],[4,7],[6,9],[8,10],[11,12]]输出
4说明
选
[1,3],[4,7],[8,10],[11,12]，共4个区间互不重叠，为最大可行数。
示例2
输入
[[1,3],[2,4],[3,3],[4,4]]输出
2说明
选
[1,3],[4,4]共2个不重叠的区间。
示例3
输入
[[3,5]]输出
1说明
只有
1个请求，可选择的个数就为1。
解题思路
核心思想
这是经典区间调度问题。为了选出最多个互不重叠区间，应优先选择结束位置最早的请求，因为它会给后续请求留下最大的可用空间。
算法步骤
- 将所有请求按右端点
Ri从小到大排序。 - 选择排序后的第一个请求，记录它的右端点
lastRight。 - 继续遍历后续请求：
- 若当前请求左端点
Li > lastRight，说明与已选最后一个请求不重叠，可以选择； - 否则跳过当前请求。
- 若当前请求左端点
- 返回选择的请求数量。
复杂度分析
设请求数量为 n。
- 时间复杂度：
O(n log n)，主要来自排序。 - 空间复杂度：
O(1)或O(n)，取决于排
版权声明：
作者：魔改工程师
链接：https://www.sylblog.xin/archives/829
文章版权归作者所有，未经允许请勿转载。
THE END
