Set Cover Greedy Pick

Problem

Solve a set cover instance greedily. The universe is the integers 0 to universe_size - 1 and sets is a list of lists of covered elements.

While some element is uncovered, pick the set covering the most uncovered elements (ties broken by smallest index) and record its index. Return the picked indices in order, or [] when some element appears in no set.

Hint

Greedy set cover is an ln(n) approximation: always grab the most new elements.

Test cases

case 1

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

expected: [0,2]

case 2

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

expected: [0,3]

case 3

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

expected: []

case 4

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

expected: [0,1]

Starter codePython

def greedy_set_cover(universe_size, sets):
    # Your code here
    pass

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