0
$\begingroup$

You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays.

The goal is to partition those arrays into K groups such that:

  1. Arrays grouped together don't share any integer
  2. I want to minimize the number of groups

Example:

Input: [[1, 2, 3], [2, 4, 5], [6, 7, 8], [4, 6, 10]]

Suboptimal Solution using 3 groups:

  • group 1: [[1, 2, 3], [6, 7, 8]]
  • group 2: [[2, 4, 5]]
  • group 3: [[4, 6, 10]]

Optimal Solution using 2 groups:

  • group 1: [[1, 2, 3], [4, 6, 10]]
  • group 2: [[2, 4, 5], [6, 7, 8]]

Any idea on how to solve this effectively?

$\endgroup$
2
  • 2
    $\begingroup$ There's no polynomial time algorithm, you can quite easily reduce this to the minimum clique cover problem. $\endgroup$ – orlp Oct 6 '20 at 2:50
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. There is a difference between effectively (having the effect under consideration) and efficiently (low effort in relation to effect and problem size). $\endgroup$ – greybeard Oct 7 '20 at 7:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.