Bin-Pack Pods onto Nodes

Problem Statement

The Kubernetes scheduler places a pod in two phases: filter the nodes that can fit the pod's resource requests, then score the survivors and pick the best. Reimplement that loop for a small cluster and report where every pod lands, which pods are stuck Pending, and how much capacity is left.

Background

A pod's requests are what the scheduler reserves — a node fits a pod only when its remaining CPU and remaining memory are both at least the pod's request. Nothing is overcommitted at schedule time.

Scoring here is the default LeastAllocated strategy: prefer the node with the most remaining CPU, so load spreads out instead of stacking on one machine. Ties go to the node that appears earlier in nodes.

Pods are processed strictly in the order given (a queue, one pod at a time), and each placement immediately shrinks that node's remaining capacity for the pods that follow. A pod that fits nowhere is unschedulable and reserves nothing — later, smaller pods can still be placed.

CPU is in millicores, memory in MiB, both integers.

Your Task

Implement:

def schedule_pods(nodes, pods):

Return a dict with keys, in this order:

• "placements": list of [pod_name, node_name] pairs, in the order pods were placed.
• "unschedulable": list of pod names that never fit, in input order.
• "remaining": list of [node_name, cpu_left, memory_left], one per node in the input node order.

Input Format

• nodes: list of dicts with "name", "cpu", "memory".
• pods: list of dicts with "name", "cpu", "memory".

Output Format

• The dict described above; all numbers are ints.

Sample

nodes = [{"name": "node-a", "cpu": 4000, "memory": 8192},
         {"name": "node-b", "cpu": 4000, "memory": 8192}]
pods = [{"name": "infer-1", "cpu": 1500, "memory": 2048},
        {"name": "infer-2", "cpu": 1500, "memory": 2048}]
print(schedule_pods(nodes, pods))

Output:

{'placements': [['infer-1', 'node-a'], ['infer-2', 'node-b']], 'unschedulable': [], 'remaining': [['node-a', 2500, 6144], ['node-b', 2500, 6144]]}

Both nodes tie on the first pod so node-a wins on order. That leaves node-a with 2500m against node-b's 4000m, so the second pod spreads to node-b.