Skip to the content

A fully covered night shift

Problem

Tonight the hospital's on-call shift has to cover several specialties, and Dr. Carmen Villalobos is making phone calls. Each available doctor covers some specialties. She does not want to wake anyone up for nothing: she is looking for the smallest group that, between them, covers everything that is missing.

Write a function that takes missing, a list of strings with the specialties still needed (no repeats; it may be empty), and doctors, a list where each element is the list of specialties one doctor covers, like ["pediatrics", "urology"] (it may include specialties nobody asked for; the list of doctors may be empty). Return a whole number: the fewest doctors you need to call so that every specialty in missing is covered by at least one of them. If even calling everyone does not cover them, return -1.

For example, cardiology, neurology, pediatrics, trauma, gynecology and orthopedics are missing, and there are three doctors. The first covers pediatrics, trauma, gynecology and orthopedics; the second, cardiology, pediatrics and gynecology; the third, neurology, trauma and orthopedics. Calling the second and the third is enough: it returns 2. If no specialty is missing, there is no one to call: it returns 0.

Examples

  • The example

    ["cardiology", "neurology", "pediatrics", "trauma", "gynecology", "orthopedics"], [["pediatrics", "trauma", "gynecology", "orthopedics"], ["cardiology", "pediatrics", "gynecology"], ["neurology", "trauma", "orthopedics"]] → 2

  • Nobody covers neurology

    ["cardiology", "neurology"], [["cardiology"], ["cardiology", "orthopedics"]] → -1

  • A single doctor covers everything

    ["cardiology", "neurology", "pediatrics"], [["neurology"], ["pediatrics", "neurology", "cardiology"], ["cardiology"]] → 1

  • No specialty is missing

    [], [["cardiology"]] → 0

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

Python

def calls(missing, doctors):
    pass

JavaScript

function calls(missing, doctors) {
}
Solve this challenge

It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.

More O(2ⁿ) challenges

See all challenges →