Best Fit Memory Allocation is a classic greedy problem from operating systems. You have a list of free memory blocks and a process that needs some amount of memory. The greedy rule: place the process in the smallest block that still fits, so the wasted leftover is as small as possible.
Problem. You are given blocks, a list of free-memory sizes, and a process of size size. Choose
the block to place the process in using Best Fit: among all blocks large enough, pick the one with
the smallest leftover (block - size). Return its index, or -1 if none fits.
Example: blocks = [100, 500, 200, 300], size = 212 → answer 3 (block 300 fits with leftover
88, smaller than block 500 which leaves 288).
The slow way first
You might grab the first block that fits (that is "First Fit"). For size = 212 that would be block 500, leaving a wasteful 288 units stranded. First Fit is fast but it scatters big holes. The question to ask: of every block that fits, which one leaves the least waste? Answering that means looking at all of them and keeping the best.
The idea: keep the tightest fit
Walk every block once. Skip any block too small to hold the process. Among the blocks that fit, track the one whose leftover block - size is the smallest seen so far. When the scan ends, that index is the best fit. Greedy works here because each placement only cares about minimizing this single process's waste.
The key insight: a block only becomes the new best when its leftover is strictly smaller than the best leftover so far. The first fitting block seeds the best; later, tighter blocks replace it.
Walk through it
Step through the animation. Block 100 is too small, so we skip it. Block 500 fits with leftover 288 — our first candidate. Block 200 is too small. Block 300 fits with leftover 88, which beats 288, so block 3 becomes the best fit. After the scan we place the process in block 3 and shrink it from 300 to 88.
Pseudocode
best = -1
best_left = infinity
for each index i with size cap in blocks:
if cap < size:
continue # too small, skip
left = cap - size
if left < best_left: # tighter fit than anything so far
best_left = left
best = i
if best == -1:
return -1 # nothing fit
blocks[best] -= size # place the process, shrink the block
return bestThe Python solution
def best_fit(blocks, size):
best = -1
best_left = float("inf")
for i, cap in enumerate(blocks):
if cap < size:
continue
left = cap - size
if left < best_left:
best_left = left
best = i
if best == -1:
return -1
blocks[best] -= size
return bestbestholds the index of the tightest fit so far;best_leftis its leftover, starting at infinity.enumerategives us both the indexiand the block sizecapas we scan.if cap < size: continueskips any block too small to hold the process.left = cap - sizeis the wasted space if we placed the process here.- Line 8 is the greedy heart: we keep a block only when its leftover beats the best so far.
- After the loop,
best == -1means nothing fit; otherwise we shrink the chosen block and return its index.
Complexity
| Case | Time | Notes |
|---|---|---|
| Single placement | O(n) (moderate) | one scan over n blocks |
| Placing m processes | O(m·n) (moderate) | a scan per process |
O(1) (fast)We do one linear pass per process and keep only two variables, so the extra space is O(1). A heap can speed repeated placements, but the plain scan is what interviewers expect first.
When this pattern shows up
Whenever a problem says "choose the option that minimizes (or maximizes) some quantity," reach for a single greedy scan that tracks the best candidate so far. Best Fit, "minimum/maximum element with a condition," and "closest value that satisfies a constraint" are all the same move.
Use a strict less-than when updating the best. With <= you would needlessly jump to a later block
with the same leftover, and forgetting to skip blocks that are too small lets a negative leftover sneak
in and look like the tightest fit.
Practice
For blocks = [100, 500, 200, 300] and size = 212, after checking block 500 (leftover 288), what happens when we reach block 300?
1. What does Best Fit choose among all blocks that fit?
2. Why do we skip blocks where cap < size?
3. Why use strict < when updating the best block?
4. What is the time cost of placing m processes into n blocks with this scan?