1type Sets = Record<string, Set<string>>;
2
3/**
4 * Жадное покрытие множеств.
5 * На каждом шаге выбирает подмножество, покрывающее максимум ещё непокрытых элементов.
6 *
7 * @param universe Вселенная элементов (что нужно покрыть)
8 * @param sets Набор подмножеств по имени
9 * @returns Имена выбранных множеств в порядке выбора
10 *
11 * @complexity Время: O(k · n · m), Память: O(m)
12 * @note Если покрытие невозможно (остались непокрытые элементы), алгоритм остановится раньше.
13 */
14function greedySetCover(universe: Set<string>, sets: Sets): string[] {
15  const uncovered = new Set(universe);
16  const chosen: string[] = [];
17
18  while (uncovered.size > 0) {
19    let best: string | null = null;
20    let bestCoveredCount = 0;
21    let bestCovered: Set<string> = new Set();
22
23    for (const [name, coverage] of Object.entries(sets)) {
24      // сколько новых элементов это множество покрывает сейчас
25      const coveredNow = new Set([...coverage].filter(x => uncovered.has(x)));
26      if (coveredNow.size > bestCoveredCount) {
27        best = name;
28        bestCoveredCount = coveredNow.size;
29        bestCovered = coveredNow;
30      }
31    }
32
33    if (!best) break; // больше нечем покрывать
34    // помечаем покрытые элементы как закрытые
35    for (const x of bestCovered) uncovered.delete(x);
36    chosen.push(best);
37  }
38
39  return chosen;
40}
41
42/*** Пример (классический из «Грокаем алгоритмы») ***/
43const states = new Set(['mt','wa','or','id','nv','ut','ca','az']);
44const stations: Sets = {
45  kone:   new Set(['id','nv','ut']),
46  ktwo:   new Set(['wa','id','mt']),
47  kthree: new Set(['or','nv','ca']),
48  kfour:  new Set(['nv','ut']),
49  kfive:  new Set(['ca','az']),
50};
51
52const chosen = greedySetCover(states, stations);
53console.log('chosen:', chosen); // одно из решений: [ 'ktwo', 'kfive', 'kthree', 'kone' ]
54
55// Проверка покрытия:
56const covered = new Set<string>();
57for (const name of chosen) for (const s of stations[name]) covered.add(s);
58const uncoveredLeft = [...states].filter(s => !covered.has(s));
59console.log('uncovered:', uncoveredLeft); // -> []
60