# 会議のスケジュール
schedules = {
    "meeting1": ("10:00", "13:00"),
    "meeting2": ("10:00", "12:00"),
    "meeting3": ("10:00", "11:00"),
    "meeting4": ("11:00", "13:00"),
    "meeting5": ("11:00", "12:00"),
    "meeting6": ("11:00", "15:00"),
    "meeting7": ("12:00", "16:00"),
    "meeting8": ("12:00", "15:00"),
    "meeting9": ("13:00", "15:00"),
    "meeting10": ("13:00", "14:00"),
    "meeting11": ("14:00", "17:00"),
    "meeting12": ("15:00", "19:00"),
    "meeting13": ("15:00", "17:00"),
    "meeting14": ("15:00", "16:00"),
    "meeting15": ("16:00", "18:00"),
    "meeting16": ("16:00", "18:00"),
    "meeting17": ("17:00", "19:00"),
    "meeting18": ("17:00", "18:00"),
    "meeting19": ("18:00", "19:00"),
}
    
# 会議の数
num_meetings = len(schedules)
    
# 会議室の数
num_rooms = 8

# 時刻を時間単位の数値に変換する関数
def time2num(time: str):
    h, m = map(float, time.split(":"))
    return h + m / 60

# 2つの会議時間に重なりがあるかをチェック
def check_overlap(meeting_name1: str, meeting_name2: str) -> bool:
    start1, end1 = map(time2num, schedules[meeting_name1])
    start2, end2 = map(time2num, schedules[meeting_name2])
    
    return start1 < end2 and start2 < end1

import itertools
    
# 会議名のリストを取得
mtg_names = list(schedules.keys())
    
# スケジュールの重なりがある会議のインデックスをタプルで格納
overlaps = [
    (idx1, idx2)
    for idx1, idx2 in itertools.combinations(range(num_meetings), 2)
    if check_overlap(mtg_names[idx1], mtg_names[idx2])
]

from amplify import VariableGenerator
    
gen = VariableGenerator()
q = gen.array("Binary", shape=(num_meetings, num_rooms))

from amplify import one_hot
    
room_constraints = one_hot(q, axis=1)

from amplify import equal_to, sum as amplify_sum
    
# overlaps内の全ての (i, j) で、q[i, r] * q[j, r] = 0 の制約条件を課す
overlap_constraints = amplify_sum(
    equal_to(q[i, :] * q[j, :], 0, axis=()) for (i, j) in overlaps
)

model = room_constraints + overlap_constraints

from amplify import FixstarsClient, solve
from datetime import timedelta
    
# クライアントを設定
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"  # ローカル環境で使用する場合は、Amplify AEのアクセストークンを入力してください
client.parameters.timeout = timedelta(milliseconds=1000)  # タイムアウト1秒
    
# 求解の実行
result = solve(model, client)
    
# result が空の場合、制約条件を満たす解が得られなかったことを示す
if len(result) == 0:
    raise RuntimeError("Given constraint conditions are not satisfied")

# 求めた解を元の変数に代入
solution = q.evaluate(result.best.values)
    
solution

import numpy as np
    
# room_list[i] は会議 i に割り当てられる会議室のインデックスとなる
room_list = (solution @ np.arange(num_rooms)).astype(int)
    
# 会議名と会議室インデックスの辞書を作成
room_assignment = {
    meeting_name: room_idx for meeting_name, room_idx in zip(mtg_names, room_list)
}
    
room_assignment

#
# 会議室割り当てを可視化
#
%matplotlib inline
    
import string
import matplotlib
import matplotlib.pyplot as plt
    
    
def plot_mtg_schedule():
    room_names = [f"Room {c}" for c in string.ascii_uppercase[:num_rooms]]
    
    cmap = matplotlib.colormaps["coolwarm"].resampled(num_rooms)
    
    fig, ax = plt.subplots(nrows=1, ncols=1, figsize=(15, 10))
    for mtg_name, room in room_assignment.items():
        start = time2num(schedules[mtg_name][0])
        end = time2num(schedules[mtg_name][1])
    
        ax.fill_between(
            [room + 0.55, room + 1.45],
            start,
            end,
            edgecolor="black",
            linewidth=3.0,
            facecolor=cmap(room),
        )
        ax.text(
            room + 0.6, start + 0.1, f"{schedules[mtg_name][0]}", va="top", fontsize=10
        )
        ax.text(
            room + 1.0,
            (start + end) * 0.5,
            mtg_name,
            ha="center",
            va="center",
            fontsize=15,
        )
    
    # Set First Axis
    ax.yaxis.grid()
    ax.set_xlim(0.5, len(room_names) + 0.5)
    ax.set_ylim(19.1, 7.9)
    ax.set_xticks(range(1, len(room_names) + 1))
    ax.set_xticklabels(room_names)
    ax.set_ylabel("Time")
    
    # Set Second Axis
    axis_x = ax.secondary_xaxis("top")
    axis_y = ax.secondary_yaxis("right")
    axis_x.set_xticks(ax.get_xticks())
    axis_x.set_xticklabels(ax.get_xticklabels())
    axis_y.set_ylabel("Time")
    
    plt.show()
    
    
plot_mtg_schedule()

会議 \ 会議室	会議室 A	会議室 B	$\cdots$	会議室 H
`meeting 1`	$q_{0,0}$	$q_{0,1}$	$\cdots$	$q_{0,7}$
`meeting 2`	$q_{1,0}$	$q_{1,1}$	$\cdots$	$q_{1,7}$
$\vdots$	$\vdots$	$\vdots$	$\cdots$	$\vdots$
`meeting 19`	$q_{19,0}$	$q_{19,1}$	$\cdots$	$q_{19,7}$

会議割り当て問題¶