Bin-Pack Pods onto Nodes (First-Fit Decreasing)

mediumPROKubernetes Scheduling & RolloutsSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

Estimate how many identical nodes are needed to schedule a set of pods by CPU request using first-fit-decreasing bin packing.

Background

Each node has node_cpu allocatable CPU. Pods are sorted by CPU request descending, then each is placed in the first node with enough remaining CPU; if none fits, a new node is opened. Return the number of nodes used. A pod larger than node_cpu is unschedulable — return -1.

Your Task

def pack_nodes(pod_cpus, node_cpu):

Return the node count, or -1 if any pod exceeds a node.

Input Format

pod_cpus (list of numbers), node_cpu (number).

Output Format

An int (node count) or -1.

Sample

print(pack_nodes([3, 3, 2, 2, 1], 4))

Output:

Example

Input

print(pack_nodes([3, 3, 2, 2, 1], 4))

Output

Reasoning

Check for unschedulable pods: Verify that no single pod exceeds the node capacity. Since the maximum pod CPU is $3$ and the node capacity is $4$ ( $3 \le 4$ ), all pods are schedulable, so we proceed with packing.
Sort pods in descending order: To apply the First-Fit Decreasing strategy, sort the input list $[3, 3, 2, 2, 1]$ to get $[3, 3, 2, 2, 1]$ .
Place the first two pods: The first pod ( $3$ ) does not fit in any existing node, so Node 1 is opened with remaining capacity $4 - 3 = 1$ . The second pod ( $3$ ) does not fit in Node 1 ( $1 < 3$ ), so Node 2 is opened with remaining capacity $4 - 3 = 1$ .
Place the next two pods: The third pod ( $2$ ) does not fit in Node 1 or Node 2 (both have only $1$ remaining), so Node 3 is opened with remaining capacity $4 - 2 = 2$ . The fourth pod ( $2$ ) fits into the first available node with sufficient space, which is Node 3 ( $2 + 2 \le 4$ ), updating Node 3's remaining capacity to $0$ .
Place the final pod and count nodes: The last pod ( $1$ ) fits into Node 1 (remaining $1$ ), updating Node 1's remaining capacity to $0$ . The total number of nodes used is $3$ .

The final output is 3

Constraints

Sort pods descending, first-fit into node remaining capacity.
Open a new node when none fits.
Any pod > node_cpu -> return -1.

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium

Concept primerPREVIEW

1. Background Knowledge

Bin packing is a classic combinatorial optimization problem where items of varying sizes must be packed into a finite number of bins of fixed capacity to minimize the number of bins used. It is NP-hard in its general form, meaning no known polynomial-time algorithm can find the optimal solution for all inputs. Consequently, practitioners rely on heuristics that produce good (though not always optimal) solutions quickly.

In the context of Kubernetes scheduling, each node has a fixed amount of allocatable resources (CPU, memory). Pods request specific amounts of these resources. The scheduler must assign pods to nodes such that the sum of requests on any node does not exceed its capacity. While real schedulers use complex scoring functions, the First-Fit Decreasing (FFD) heuristic is a standard baseline: sort items by size in descending order, then place each item into the first bin where it fits. FFD is simple, fast, and guarantees a solution within a constant factor of the optimal number of bins.

A critical edge case in resource allocation is oversized items. If a single pod requests more CPU than an entire node provides, it can never be scheduled, regardless of how many nodes are available. This scenario must be detected and handled explicitly, typically by returning an error code or a special value like -1.

2. Algorithm Approach

The problem explicitly requires the First-Fit Decreasing heuristic. The approach involves two main phases:

Preprocessing: Sort the list of pod CPU requests in descending order. This ensures that larger pods are placed first, which generally leads to better packing efficiency than placing smaller pods first.
Greedy Placement: Iterate through the sorted pods. For each pod, scan the list of currently open nodes (bins) in the order they were created. Place the pod in the first node that has sufficient remaining capacity. If no existing node has enough space, open a new node and place the pod there.

This is a greedy algorithm because it makes the locally optimal choice at each step (placing in the first available bin) without considering future consequences. The state of the system is tracked by the remaining capacity of each open node.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results