字节二面，挂了，简直浪费时间。。。

大家好，我是吴师兄。

昨天，我偶然间翻看一个热门讨论帖子，里面分享了一位同学参加字节跳动面试的经历，令人印象深刻的是，他的第二轮面试仅用了 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         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)

代码如下：