Fair Queue Deficit Round Robin

Problem

Simulate deficit round robin scheduling.

quantum is added to each backlogged flow's deficit every round, and a flow may send packets while its deficit covers the head packet's size. packets is a list of [flow, size] in arrival order.

Return the packet indices in service order.

Hint

Unused deficit carries over, so a flow that skipped a round can burst later.

Test cases

case 1

in: [3,[[0,2],[1,4],[0,5]]]

expected: [0,1,2]

case 2

in: [5,[[0,7],[1,2]]]

expected: [1,0]

case 3

in: [10,[[0,1],[0,1]]]

expected: [0,1]

case 4

in: [2,[]]

expected: []

Starter codePython

def deficit_round_robin(quantum, packets):
    # Your code here
    pass

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