Greedy Interval Algorithm for Memory Allocation

After an anecdote about efficient interview processes, the article introduces a classic algorithmic problem: given a total memory space of 100 bytes and a set of already allocated intervals, allocate a new block of a specified size using a greedy strategy that prefers the free segment closest in size to the request and positioned immediately after the previous allocation.

The solution first checks whether any of the existing intervals overlap; if an overlap is found the request is deemed invalid and the program outputs -1 .

To handle edge cases uniformly, two sentinel intervals [-1, 0] and [100, 101] are added to the list, representing the free space before the first allocation and after the last one. By iterating over each pair of adjacent intervals, the algorithm computes the size of the free gap ( next_start - end ) and keeps the smallest gap that is still at least as large as the requested size.

Overlap‑checking snippet:

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

Full allocation algorithm:

size = int(input())
intervals = []
while True:
    try:
        start, memory_size = map(int, input().split())
        intervals.append([start, start + memory_size])
    except:
        break

intervals.sort(key = lambda x: x[0])
isOverlap = False
for i in range(1, len(intervals)):
    if intervals[i][0] < intervals[i-1][1]:
        isOverlap = True
        break
if isOverlap:
    print(-1)
else:
    ans = -1
    free_size = 100
    intervals = [[-1, 0]] + intervals + [[100, 101]]
    for i in range(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)

The article concludes by noting that mastering such problems, together with many other classic LeetCode questions, builds a solid foundation for algorithmic interviews.