P3197. 堆内存申请

解题思路

理解题意

做出示例二对应的示意图，为：

若我们想要申请一块长度为 1 的内存，申请一块空闲大小足够且尽量靠近 1 的内存，从图上很容易看出应该选择偏移地址为 5。即：

若我们想要申请一块长度为 2 的内存，申请一块空闲大小足够且尽量靠近 2 的内存，从图上很容易看出应该选择偏移地址为 1。即：

若我们想要申请一块长度为 3 的内存，申请一块空闲大小足够且尽量靠近 3 的内存，从图上很容易看出应该选择偏移地址为 7。即：

所以在理解了题意之后，题目实际上是非常简单的。

判断区间是否重叠

首先我们需要判断所有的区间是否有重叠，如果出现重叠则需要输出 -1。

查找空闲内存

在确保没有区间存在重叠之后，则需要查看所有空闲内存，即上述图中的蓝色方块部分。找到所有蓝色方块中最接近待申请内存大小 size 的那个位置。

显然我们可以通过两个相邻间隔中，前一个间隔的 end，和后一个间隔的 start，来得到空闲内存。

我们只需要遍历所有相邻间隔，考虑空闲内存的大小，找到大于等于且最接近 size 的那块空闲内存即为答案。

处理边界情况

注意，由于空闲内存有可能出现在最开头或末尾，为了维护算法的一致性，我们可以在 intervals 数组的最开头和最末尾分别填充哨兵间隔 [-1, 0] 和 [100, 101]，注意填充的数组只有 0 和 100 是要被使用到的。

整体代码如下：

复杂度分析 设输入的已占用内存块个数为 n。算法分三段：读入并构建 intervals 数组是 O(n)；按起始地址排序是 O(n log n)；之后是两趟线性扫描——一趟检查相邻区间是否重叠判断输入是否有效，另一趟在首尾补上哨兵区间 [-1, 0] 和 [100, 101] 后遍历所有相邻区间之间的空隙、寻找大于等于 size 且最接近 size 的空闲块——各是 O(n)。总时间复杂度为 O(n log n)，瓶颈在排序。空间上需要 O(n) 存储所有区间（含两个哨兵），额外只用了 isOverlap、ans、free_size 等常数个变量。由于题中堆地址空间固定在 0 到 100 之间，区间数本身很小，这个复杂度绰绰有余。