接種枠を埋める問題

新型コロナワクチンWeb予約抽選申込フォームについてという記事に、説明用として次のような例が挙げてある。

6人の接種希望対象者A〜Fがいる。各対象者は、会場・時間帯の異なる枠1〜10のうち、希望する枠をいくつでも選べる（元記事では会場1〜5の午前・午後であったが、ここでは1〜10の通し番号とした）。1つの枠には1人しか入れない。元記事では、対象者にランダムに順位を付け、その順に枠を左から埋めていく。

しかし、実際にやってみると、うまく全員が埋まらない。埋まった枠を●で表すと、次のようになる：

順位5のDさんは枠1・6を希望したが、枠1は順位3のAさんが先に取り、枠6は順位2のFさんが先に取ってしまっているので、どこにも入れない。

しかし、AさんかDさんに別の枠に移ってもらえば、うまく全員が収まる。

このような場合にできるだけ多くの人に枠を割り振る問題は、2部グラフの最大マッチング（maximum bipartite matching）の問題と呼ばれる。

深さ優先探索による簡単な解き方（Maximum Bipartite Matching 参照）：

slots = {
    'A': [1, 3, 5, 7, 9],
    'B': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
    'C': [2, 4, 5, 6, 7, 8, 9],
    'D': [1, 6],
    'E': [3],
    'F': [6, 8]
}

order = {
    'A': 3,
    'B': 4,
    'C': 6,
    'D': 5,
    'E': 1,
    'F': 2
}

applicants = {}  # empty dict

def bpm(applicant, visited):
    for slot in slots[applicant]:
        if slot not in visited:
            visited.add(slot)
            if slot not in applicants or bpm(applicants[slot], visited):
                applicants[slot] = applicant
                return True
    return False

results = 0
for applicant in sorted(slots.keys(), key=lambda k: order[k]):
    visited = set()  # empty set
    if bpm(applicant, visited):
        results += 1

print(f"埋まった人数: {results}")
print("枠と対象者:")
for slot in sorted(applicants):
    print(f"{slot}: {applicants[slot]}")

for applicant in ... のループは、実際にはどういう順序で埋めていっても埋まる人数は同じなので、単に

for applicant in slots.keys():

でもよいが、全員が埋まらない場合はループの順序に依存するので、order の昇順に埋めていく。あるいは、順位をランダムに定めるよりは、たくさんの枠を書いてくれた人を優先するために

for applicant in sorted(slots.keys(), key=lambda k: len(slots[k]), reverse=True):

のようにするのでもよいかもしれない。