Scheduling of covid-19 vaccine in Speee, Inc

README.md

割当問題（をナイーブに解く）

inputデータのフォーマットは、以下のように定義している

${time_num}
${time_id} ${num}
...
${id} ${time_id} ${time_id} ...

• time_num: 割当可能な時間帯数
• id: 割当対象のID
• time_id: 割り当てる時間帯のID（0始まりの整数）

実行

$ python scheduling.py < sample.txt
defaultdict(<class 'list'>, {2: [1, 10, 18, 2], 0: [4, 3, 6, 9], 1: [12, 20, 7, 15], 3: [5, 8, 11, 13], 4: [14, 16, 17, 19]})

Licence

MIT Licence

sample.txt

5
0 4
1 4
2 4
3 4
4 4
1 0 1 3 4
2
3 1 2 3
4 1 2 3 4
5
6 2 4
7 3
8
9 1 2
10 0 1
11
12 0 2
13
14
15 4
16
17
18 1
19
20 2 3

scheduling.py

from collections import defaultdict

import numpy as np


if __name__ == '__main__':
    # 割当て可能な時間帯数
    time_num = int(input().strip())
    # 各時間帯による割当て可能数
    max_per_time = {}
    for i in range(time_num):
        per_time = list(map(int, input().strip().split()))
        max_per_time[per_time[0]] = per_time[1]

    # 対象と対象がNGとなる時間帯データ
    # format:
    #   ${id} ${time_id} ${time_id} ...
    #     id: 対象となるID
    #     time_id: 割当NGの時間帯のID 0〜(time_num-1)
    inputs = []
    while True:
        try:
            data = list(map(int, input().strip().split()))
            ng_times_num = len(data[1:])
            data.insert(0, ng_times_num)
        except EOFError:
            break
        inputs.append(data)

    # 制約条件の多い順にソート
    inputs = sorted(inputs, key=lambda x: -x[0])

    # 初期化
    table = np.zeros((len(inputs), time_num + 1), dtype=int)
    for i in range(len(inputs)):
        data = inputs[i][1:]
        table[i][0] = data[0]
        for j in range(len(data[1:])):
            j_ = data[1:][j] + 1
            table[i][j_] -= 1

    outputs = defaultdict(list)

    # 割当
    for i in range(len(table)):
        for j in range(len(table[i]) - 1):
            j_ = j + 1
            if (table[i][j_] == 0) and len(outputs[j]) < max_per_time[j]:
                outputs[j].append(table[i][0])
                break

    print(outputs)