Weighted Fair Queue Credits

Problem

Compute weighted fair queueing finish times for packets.

packets is a list of [flow, size] in arrival order and weights gives each flow's weight. A packet's virtual start is the later of the current virtual time and its flow's previous finish, and its virtual finish is the start plus size divided by the weight. Order packets by finish time, breaking ties by arrival index.

Return the packet indices in service order.

Hint

Each flow's finish times are non-decreasing, so the next packet starts where the previous one ended.

Test cases

case 1

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

expected: [0,1,2]

case 2

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

expected: [0,1]

case 3

in: [[[0,3],[1,1]],[1,3]]

expected: [1,0]

case 4

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

expected: [0,2,1]

Starter codePython

def wfq_finish_times(packets, weights):
    # Your code here
    pass

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