字节二面，挂了，简直浪费时间。。。
大家好，我是吴师兄。
昨天，我偶然间翻看一个热门讨论帖子，里面分享了一位同学参加字节跳动面试的经历，令人印象深刻的是，他的第二轮面试仅用了 25 分钟便宣告结束，并迅速得到了结果，效率确实高效。
这种高效明快的面试模式，无疑是许多求职者梦寐以求的。
想象一下，如果你有一整个上午或下午的时间，按照这样的效率，完全有可能参加至少两场面试，大大增加了找到理想工作的机会。
然而，现实往往不尽人意。
也有同学反映，他们的面试经历长达 75 分钟甚至 2 个小时，最终却以失败告终，有点浪费双方的时间。
话说回来，面试或许就是一个屡败屡战的过程，多准备多复盘才能拿到理想的 offer。
回到今天的正题，来学习和练习一道区间贪心的算法题。
题目描述是这样的：有一个总空间为100字节的堆，现要从中新申请一块内存，内存分配原则为优先紧接着前一块已使用内存分配空间、足够数目最接近申请大小的空闲内存。
做出示例二对应的示意图，为
若我们想要申请一块长度为1的内存，申请一块空闲大小足够且尽量靠近1的内存，从图上很容易看出应该选择偏移地址为5。即
若我们想要申请一块长度为2的内存，申请一块空闲大小足够且尽量靠近2的内存，从图上很容易看出应该选择偏移地址为1。即
若我们想要申请一块长度为3的内存，申请一块空闲大小足够且尽量靠近3的内存，从图上很容易看出应该选择偏移地址为7。即
所以在理解了题意之后，题目实际上是非常简单的。
首先我们需要判断所有的区间是否有重叠，如果出现重叠则需要输出-1。
intervals.sort(key = lambda x: x[0])
isOverlap = False
for i in range(1, len(intervals)):
start = intervals[i][0]
pre_end = intervals[i-1][1]
if start < pre_end:
isOverlap = True
break
在确保没有区间存在重叠之后，则需要查看所有空闲内存，即上述图中的蓝色方块部分。找到所有蓝色方块中最接近待申请内存大小size的那个位置。
显然我们可以通过两个相邻间隔中，前一个间隔的end，和后一个间隔的start，来得到空闲内存。
我们只需要遍历所有相邻间隔，考虑空闲内存的大小，找到大于等于且最接近size的那块空闲内存即为答案。
注意，由于空闲内存有可能出现在最开头或末尾，为了维护算法的一致性，我们可以在intervals数组的最开头和最末尾分别填充哨兵间隔[-1, 0]和[100, 101]，注意填充的数组只有0和100是要被使用到的。
整体代码如下
ans = -1
free_size = 100
intervals = [[-1, 0]] + intervals + [[100, 101]]
for i in range(0, len(intervals)-1):
end = intervals[i][1]
nxt_start = intervals[i+1][0]
if free_size > nxt_start - end >= size:
ans = end
free_size = nxt_start - end
print(ans)
代码如下：
# 输入将分配的内存的大小
size = int(input())
# 储存所有间隔
intervals = list()
# 行数未知，使用try-except语句进行输入
while True:
try:
# 输入某块内存的起始位置、长度
start, memory_size = map(int, input().split())
# 记录该间隔
intervals.append([start, start + memory_size])
except:
break
# 检查所输入的间隔是否存在重叠，若存在，则判定为无效申请，直接输出-1
# 将所有间隔按照起始位置start排序
intervals.sort(key = lambda x: x[0])
# 设置一个标志
isOverlap = False
# 遍历所有相邻间隔，如果出现第i个间隔的start位于第i-1个间隔的end之前
# 即出现了重叠，将isOverlap标记为True
for i in range(1, len(intervals)):
start = intervals[i][0]
pre_end = intervals[i-1][1]
if start < pre_end:
isOverlap = True
break
# 如果出现重叠，说明是无效输入，直接输出-1
if isOverlap:
print(-1)
else:
ans = -1
# 初始化最接近size的空闲内存的大小为一个较大数
# 用来维护遍历过程中，找到所有空闲内存中最接近size的那个
free_size = 100
# 往intervals的前面和后面分别添加区间[-1, 0]和[100, 101]
# 这个技巧能够维护最开始的空闲内存和最后的那段空闲内存，都能保持一致性
# 此时某个间隔的end和下一个间隔的start，会构成一个空闲内存
intervals = [[-1, 0]] + intervals + [[100, 101]]
# 考虑所有间隔和其下一个间隔（所有相邻间隔）
for i in range(0, len(intervals)-1):
end = intervals[i][1]
nxt_start = intervals[i+1][0]
# 当当前空闲内存满足以下两个条件：
# 1. 大于等于待分配的内存size
# 2. 小于之前记录过的最大空闲内存大小（更接近size）
# 则更新答案为end，同时更新free_size
if free_size > nxt_start - end >= size:
ans = end
free_size = nxt_start - end
print(ans)
腾讯云开发者
