一、真题

题目描述：

有一个总空间为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

输出：

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

二、解题思路图解💡

步骤 1：数据清洗与校验

1. 读取所有已分配块，存储为对象/结构体列表。
2. 校验逻辑：
   • offset < 0 或 size <= 0 →→ 非法。
   • offset + size > 100 →→ 越界，非法。
   • 重叠检测：将已分配块按 offset 排序，遍历检查 current.offset < prev.offset + prev.size。若成立，则重叠，非法。
   • 若任何校验失败，直接输出 -1。

步骤 2：构建空闲区间列表

假设已分配块已按 offset 升序排序：[B1, B2, ..., Bn]。
空闲块来源于三部分：

1. 头部空闲：若 B1.offset > 0，则存在空闲块 [0, B1.offset)，长度 B1.offset。
2. 中间空闲：遍历 i 从 0 到 n-2，若 B[i].offset + B[i].size < B[i+1].offset，则存在空闲块 [B[i].end, B[i+1].offset)，长度 B[i+1].offset - B[i].end。
3. 尾部空闲：若 Bn.end < 100，则存在空闲块 [Bn.end, 100)，长度 100 - Bn.end。

步骤 3：贪心匹配 (Best Fit)

遍历所有生成的空闲块：

• 若 free.size < reqSize：跳过。
• 若 free.size >= reqSize：
  • 记录当前差值 diff = free.size - reqSize。
  • 维护一个全局最小差值 minDiff 和对应的最佳偏移 bestOffset。
  • 若 diff < minDiff，更新 minDiff 和 bestOffset。
  • (进阶)：若 diff == minDiff，通常选择偏移地址更小的（题目示例未涉及冲突，但代码中可加上此逻辑保证确定性）。

步骤 4：输出结果

• 若找到 bestOffset，输出该值。
• 若未找到（即没有足够大的空闲块），输出 -1。

---

三、Java 语言实现

import java.util.*;
import java.io.*;

public class MemoryAllocation {

    static class Block implements Comparable<Block> {
        int offset;
        int size;
        int end;

        public Block(int offset, int size) {
            this.offset = offset;
            this.size = size;
            this.end = offset + size;
        }

        @Override
        public int compareTo(Block o) {
            return Integer.compare(this.offset, o.offset);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取申请大小
        if (!scanner.hasNextInt()) {
            System.out.println("-1");
            return;
        }
        int reqSize = scanner.nextInt();
        if (reqSize <= 0) {
            System.out.println("-1");
            return;
        }

        List<Block> allocated = new ArrayList<>();
        
        // 读取已分配内存
        while (scanner.hasNextInt()) {
            int offset = scanner.nextInt();
            if (!scanner.hasNextInt()) {
                // 格式错误：有offset没size
                System.out.println("-1");
                return;
            }
            int size = scanner.nextInt();
            allocated.add(new Block(offset, size));
        }

        // 1. 基础校验与排序
        Collections.sort(allocated);

        for (Block b : allocated) {
            // 校验负数、零大小
            if (b.offset < 0 || b.size <= 0) {
                System.out.println("-1");
                return;
            }
            // 校验越界
            if (b.end > 100) {
                System.out.println("-1");
                return;
            }
        }

        // 2. 重叠检测
        for (int i = 1; i < allocated.size(); i++) {
            Block prev = allocated.get(i - 1);
            Block curr = allocated.get(i);
            // 如果当前块的起点小于前一块的终点，说明重叠
            // 注意：题目说"紧接着"，通常意味着 [0,1) 和 [1,2) 是不重叠的，所以用 < 而不是 <=
            if (curr.offset < prev.end) {
                System.out.println("-1");
                return;
            }
        }

        // 3. 生成空闲块并寻找最佳适配
        int bestOffset = -1;
        int minDiff = Integer.MAX_VALUE;

        int currentPos = 0;

        for (Block b : allocated) {
            if (b.offset > currentPos) {
                // 发现空闲块 [currentPos, b.offset)
                int freeSize = b.offset - currentPos;
                if (freeSize >= reqSize) {
                    int diff = freeSize - reqSize;
                    if (diff < minDiff) {
                        minDiff = diff;
                        bestOffset = currentPos;
                    } else if (diff == minDiff && bestOffset == -1) {
                         // 理论上不会发生，因为是从左到右遍历，先遇到的offset更小
                         bestOffset = currentPos;
                    }
                }
            }
            currentPos = b.end;
        }

        // 检查尾部空闲
        if (currentPos < 100) {
            int freeSize = 100 - currentPos;
            if (freeSize >= reqSize) {
                int diff = freeSize - reqSize;
                if (diff < minDiff) {
                    minDiff = diff;
                    bestOffset = currentPos;
                }
            }
        }

        System.out.println(bestOffset);
    }
}

Java 代码亮点

• 面向对象设计：使用 Block 类封装偏移和大小，逻辑清晰。
• 流式处理：利用 Scanner 动态读取不定行数输入。
• 严谨的边界检查：涵盖了负数、越界、重叠、格式错误等所有异常场景。
• 一次遍历：在生成空闲块的同时进行贪心比较，无需额外存储空闲块列表，空间复杂度 O(1)O(1) （不计输入存储）。

---

 四、Go 语言实现

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

type Block struct {
	Offset int
	Size   int
	End    int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	// 读取第一行：申请大小
	if !scanner.Scan() {
		fmt.Println("-1")
		return
	}
	reqSizeStr := strings.TrimSpace(scanner.Text())
	reqSize, err := strconv.Atoi(reqSizeStr)
	if err != nil || reqSize <= 0 {
		fmt.Println("-1")
		return
	}

	var allocated []Block

	// 读取后续行：已分配内存
	for scanner.Scan() {
		line := strings.TrimSpace(scanner.Text())
		if line == "" {
			continue
		}
		parts := strings.Fields(line)
		if len(parts) != 2 {
			// 格式错误
			fmt.Println("-1")
			return
		}

		offset, err1 := strconv.Atoi(parts[0])
		size, err2 := strconv.Atoi(parts[1])

		if err1 != nil || err2 != nil {
			fmt.Println("-1")
			return
		}

		allocated = append(allocated, Block{
			Offset: offset,
			Size:   size,
			End:    offset + size,
		})
	}

	// 1. 排序
	sort.Slice(allocated, func(i, j int) bool {
		return allocated[i].Offset < allocated[j].Offset
	})

	// 2. 校验
	for _, b := range allocated {
		if b.Offset < 0 || b.Size <= 0 || b.End > 100 {
			fmt.Println("-1")
			return
		}
	}

	// 3. 重叠检测
	for i := 1; i < len(allocated); i++ {
		if allocated[i].Offset < allocated[i-1].End {
			fmt.Println("-1")
			return
		}
	}

	// 4. 贪心查找最佳适配
	bestOffset := -1
	minDiff := 101 // 最大可能差值不会超过100
	currentPos := 0

	for _, b := range allocated {
		if b.Offset > currentPos {
			freeSize := b.Offset - currentPos
			if freeSize >= reqSize {
				diff := freeSize - reqSize
				if diff < minDiff {
					minDiff = diff
					bestOffset = currentPos
				}
			}
		}
		currentPos = b.End
	}

	// 检查尾部
	if currentPos < 100 {
		freeSize := 100 - currentPos
		if freeSize >= reqSize {
			diff := freeSize - reqSize
			if diff < minDiff {
				minDiff = diff
				bestOffset = currentPos
			}
		}
	}

	fmt.Println(bestOffset)
}

Go 代码亮点

• 高效 IO：使用 bufio.Scanner 处理标准输入，适合处理多行数据。
• 切片操作：利用 sort.Slice 匿名函数轻松实现结构体排序。
• 错误处理：对 strconv.Atoi 的返回值进行严格判断，确保输入数字合法。
• 逻辑简洁：Go 的语法特性使得区间遍历和条件判断非常直观，执行效率高。

---

五、易错点总结⚠️

1. 重叠的定义：[0, 1) 和 [1, 2) 是不重叠的。代码中必须使用 < 来判断重叠（curr.start < prev.end），如果用 <= 会误判相邻块为重叠。
2. 空输入处理：如果没有已分配内存行，程序应能正确处理，此时整个 0-100 都是空闲块。上述代码逻辑天然支持（循环不执行，直接进入尾部检查）。
3. 相等长度的选择：题目要求“最接近”，若有两个空闲块长度一样且都最小（例如都需要 2，有两个长度为 2 的空闲块），通常选择偏移地址较小的。上述代码从左向右遍历，天然保证了这一点（只有 diff < minDiff 才更新，相等时不更新，保留了前面的小偏移）。
4. 非法值检测：题目备注提到“非法值”，包括负数、非整数等，代码中必须包含 try-catch (Java) 或 error 检查 (Go)。

---

六、复杂度分析📊

• 时间复杂度：
  • 排序： O(Nlog⁡N) ，其中 N 是已分配块的数量。
  • 遍历扫描： O(N) 。
  • 总体： O(Nlog⁡N)。对于 N 较小的情况（通常机考题 N 不会极大），效率极高。
• 空间复杂度：
  • O(N) 用于存储已分配块列表。
  • 若使用流式处理且不存储（需预排序则不可行，但本题需排序检测重叠，故必须存储），空间主要为输入存储。

---

八、结语

这道题是贪心算法与区间管理的经典结合。它不仅考察了基本的逻辑思维能力，还考验了对边界条件和异常输入的鲁棒性处理。

• Java 选手：注意 Scanner 的混合读取技巧和 ArrayList 的使用。
• Go 选手：享受切片和标准库带来的简洁，注意 strconv 的转换陷阱。

掌握这种“排序 -> 扫描 -> 贪心”的三段式解法，你将能轻松应对各类资源分配、区间覆盖类的机考题目。祝大家代码一遍过，Offer 拿到手软！