华为od（D卷） 堆内存申请

题目描述

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

输入描述

第1行是1个整数，表示期望申请的内存字节数。
第2到第N行是用空格分割的两个整数，表示当前已分配的内存的情况，每一行表示一块已分配的连续内存空间，每行的第1个和第2个整数分别表示偏移地址和内存块大小，如:
0 1
3 2
表示0偏移地址开始的1个字节和3偏移地址开始的2个字节已被分配，其余内存空闲。

输出描述

若申请成功，输出申请到内存的偏移
若申请失败，输出-1。

备注
1.若输入信息不合法或无效，则申请失败

2.若没有足够的空间供分配，则申请失败

3.堆内存信息有区域重叠或有非法值等都是无效输入

示例1

输入：
1
0 1
3 2

输出：
1

说明
堆中已使用的两块内存是偏移从0开始的1字节和偏移从3开始的2字节，空闲的两块内存是偏移从1开始2个字节和偏移从5开始95字节根据分配原则，新申请的内存应从1开始分配1个字节，所以输出偏移为1。

思路

代码

public class Demo19 {public static void main(String[] args) {// 检查空闲区域是否能满足申请int heapSize = 100;  // 总堆大小int lastOffsetEnd = 0;Scanner scanner = new Scanner(System.in);// 读取期望的内存字节数int requestSize = Integer.parseInt(scanner.nextLine());if (requestSize > heapSize) {System.out.println(-1);}List<int[]> allocatedBlocks = new ArrayList<>();// 读取已分配的内存块信息String in = scanner.nextLine();while (!in.equals("")) {int[] ints = Arrays.stream(in.split(" ")).mapToInt(Integer::parseInt).toArray();int offset = ints[0];int size = ints[1];allocatedBlocks.add(new int[] {offset, size});in = scanner.nextLine();}allocatedBlocks.sort(Comparator.comparingInt(a -> a[0]));// 检查非法输入，如堆内存块重叠或偏移、大小不合法if (!isValidInput(allocatedBlocks)) {System.out.println(-1);return;}// 遍历已分配块，检查相邻块之间的空闲区域for (int[] block : allocatedBlocks) {int currentOffset = block[0];int currentSize = block[1];// 计算当前块之前的空闲空间大小int freeSpace = currentOffset - lastOffsetEnd;// 如果空闲空间足够，返回起始偏移if (freeSpace >= requestSize) {System.out.println(lastOffsetEnd);return;}// 更新上一个内存块的结束位置lastOffsetEnd = currentOffset + currentSize;}// 检查最后一个块之后的空闲空间if (heapSize - lastOffsetEnd >= requestSize) {System.out.println(lastOffsetEnd);} else {System.out.println(-1);}}// 检查输入是否合法private static boolean isValidInput(List<int[]> allocatedBlocks) {for (int i = 1; i < allocatedBlocks.size(); i++) {int[] prevBlock = allocatedBlocks.get(i - 1);int[] currentBlock = allocatedBlocks.get(i);// 检查是否有重叠或者非法大小if (currentBlock[0] < prevBlock[0] + prevBlock[1] || currentBlock[1] <= 0) {return false;}}return true;}
}