Vaccination Target Set Greedy

Problem

Choose k nodes to vaccinate by highest degree, breaking ties by smallest index.

Return the chosen node indices sorted in ascending order. n is the number of nodes and edges is a list of [u, v] pairs.

Hint

Degree centrality is a simple but effective first guess for immunization.

case 1

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

expected: [0,1]

case 2

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

expected: [0]

case 3

in: [3,[],2]

expected: [0,1]

case 4

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

expected: [0,1,2,3]

Starter codePython

def vaccination_targets(n, edges, k):
    # Your code here
    pass

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