华为OD统一考试 -堆内存申请

题目描述

有一个总空间为100字节的堆，现要从中新申请一块内存，内存分配原则为：优先紧接着前一块已使用内存，分配空间足够且最接近申请大小的空闲内存。

输入描述

第1行是1个整数，表示期望申请的内存字节数

第2到第N行是用空格分割的两个整数，表示当前已分配的内存的情况，每一行表示一块已分配的连续内存空间，每行的第1和第2个整数分别表示偏移地址和内存块大小，如：

0 1

3 2

表示 0 偏移地址开始的 1 个字节和 3 偏移地址开始的 2 个字节已被分配，其余内存空闲。

输出描述

若申请成功，输出申请到内存的偏移；

若申请失败，输出 -1。

备注

1. 若输入信息不合法或无效，则申请失败
2. 若没有足够的空间供分配，则申请失败
3. 堆内存信息有区域重叠或有非法值等都是无效输入

用例

题目解析

用例图示如下：

黄色表示从第2行开始输入的内存占用情况

绿色表示对应第1行的申请到的内存

本题我的解题思路如下：

首先收集所有的已分配的内存（第2行~最后一行），然后将这些已分配内存按照起始位置升序排序。我们假设升序后的已分配内存为 used_memory。

然后，定义一个 free_offset，用于记录当前已分配内存的上一个空闲内存块的起始位置，比如

free_offset初始化为0。

之后，开始遍历 used_memory，每遍历一个已分配内存块，我们会得到如下信息：

• used.offset，当前已分配内存块的起始位置
• used.size，当前已分配内存块的大小

下面需要对于used.offset和used.size进行判断：

• 如果 used.offset < free_offset，则说明已分配内存块之间存在区域重叠，此时需要返回-1
• 如果 used.offset > 99，则说明越界，因为当前堆只有100个字节，即最大偏移（起始位置）为99，此时应该返回-1
• 如果 used.size <= 0，则说明占用的内存非法，返回-1
• 如果 used.size > 100 - used.offset，则说明占用的内存无效，即起始位置为used.offset的内存块，最大占用内存大小为 100 - used.offset，如果超过，则返回-1

如果used.offset和used.size都合法，则我们可以比较used.offset 和 free_offset，如果 used.offset > free_offset，则 [free_offset, used.offset - 1] 这个闭区间范围内是空闲内存块，比如下图所示：

该空闲内存块的大小为： used.offset - free_offset

我们判断下该空闲内存块大小是否 ≥ 申请内存，若是，则继续判断该空闲内存块大小是否最接近 申请内存，若是，则记录此时的free_offset为一个可能解

接下来，更新 free_offset = used.offset + used.size，即如下图所示：

之后继续遍历下一个used_memory，重复上面逻辑。

需要注意收尾操作，即如下图所示：

当遍历完used_memory后，free_offset会如上图所示指向最后一块空闲内存起始位置，此时该空闲内存块大小为 100 - free_offset，我们需要判断下这个空闲内存块是不是足够申请内存，且是最接近申请内存大小的。

import Foundation

struct Memory {
    var offset = 0 // 内存块起始位