I have two 2D arrays: $ P[n][s]$ and $ C[n][s]$ , $ s \leq n$ .

P contains sets of nodes and $ C$ the cost of a set in $ P$ , e.g. the cost of $ P[2][2]$ is $ C[2][2]$ and a set $ p \in P = \{ s_0, s_1, …, s_{n-1} \}^q, q \leq n$ , e.g. $ p=\{s_0, s_3\}$ .

For every row I can pick at most one set but in the end the union of the picked sets needs to contain all nodes $ \{s_0, s_1, …, s_{n-1} \}$ .

How do I find the least expensive picks in linear time?