题目内容

大语言模型推理时，显存中有一个 KV Cache，用于存储各请求的键值对。现有 $N$ 个推理请求排队，第 $i$ 个请求需要占用 KV Cache 中一段连续位置 $[L_i, R_i]$。每个位置同一时间只能分配给一个请求。请选出尽可能多的请求，使它们的区间互不重叠，从而最大化批次的吞吐量。

输入描述

• requests：由 $N$ 个推理请求构成的二维数组，requests[i] 表示第 $i$ 个推理请求，其内容为 $[L_i, R_i]$。
• 数组长度 $N$ 满足 $1 \le N \le 10^5$。
• 每个位置 $[L_i, R_i]$ 满足 $0 \le L_i \le R_i \le 10^9$。

输出描述

• 一个整数，表示最多可选多少个不重叠区间的请求。

样例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。

补充说明

• [1, 3] 和 [3, 5] 被认为是重叠。