Dynamic Batch Admission

Problem

Admit requests greedily into a batch with a token budget: walk the lengths in order and stop before the request that would exceed max_tokens, with the guarantee that at least one request is always admitted.

The signature is dynamic_batch_admit(max_tokens, lengths). Return the number of admitted requests.

Hint

Token-budget scheduling keeps every step's compute roughly constant.

Test cases

case 1

in: [1000,[100,200,300,500]]

expected: 3

case 2

in: [500,[400,400]]

expected: 1

case 3

in: [100,[50,50]]

expected: 2

case 4

in: [1000,[200,200,200,200,200]]

expected: 5

case 5

in: [100,[200,50]]

expected: 1

Starter codePython

def dynamic_batch_admit(max_tokens, lengths):
    # Your code here
    pass

5 test cases · run your code against them in the editor