企业官网建设流程全解析

目录

题目

思路

Code

题目

题目内容：

大语言模型推理时，显存中有一个 KV Cache，用于存储各请求的键值对。现有 N 个推理请求排队，第 i 个请求需要占用 KV Cache 中一段连续位置 [Li,Ri]。每个位置同一时间只能分配给一个请求。

请选出尽可能多的请求，使它们的区间互不重叠，从而最大化批次吞吐量。若两个闭区间端点相接，则共享端点位置，仍视为重叠。

输入描述：

输入为一行二维数组，每个元素为 [Li,Ri]。满足 1 <= N <= 100000，0 <= Li <= Ri <= 1000000000。

输出描述：

输出最多可选的不重叠请求数量。

样例 1

输入：

[[1,3],[2,5],[4,7],[6,9],[8,10],[11,12]]

输出：

4

说明：

可以选择 [1,3]、[4,7]、[8,10]、[11,12]。

思路

整体思路：这是最大不重叠闭区间数量问题，按结束位置最早优先选择。

第一步：将全部请求按右端点升序排序，右端点相同时按左端点排序即可。