Skip to content

Instantly share code, notes, and snippets.

@yoppi

yoppi/README.md Secret

Last active Jun 28, 2021
Embed
What would you like to do?
Scheduling of covid-19 vaccine in Speee, Inc

割当問題(をナイーブに解く)

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]})
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
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment