Python-會議安排

Question

求該題程式碼

某公司有數間大小不同的會議室，可容納的人數不同，使用會議前需要各單位登記舉辦會議時間，會議室24小時開放，每個會議有不同的使用時間。由於會議眾多，可能發生時間衝突或會議人數超過會議室可容納人數上限，總務部門需從這些會議中，選取時間上不衝突，且可以容納會議人數的會議室，讓他們能夠如願使用會議室。公司希望所有會議室能做最有效的利用。

另外公司政策表明，為避免與會來賓需頻繁更換會議室，
每一場會議要安排在能容納會議人數的會議室，且一定要在同一個會議室
(詳細說明請看範例2)

輸入說明：
第一行輸入兩個整數M, N，M是會議室間數，N是申請舉辦會議個數。
其中 1 <= M <= 4 ， 1 <= N <= 10 。
其後M行，每一行有兩個正整數以空白隔開，代表會議室編號、可容納人數；
其後N 行，每一行有四個正整數以空白隔開，代表每一個申請會議的編號、會議人數、開始時間(0-23)、結束時間(1-24)。

時間以0代表凌晨12點，18代表下午六點，24代表半夜12點
例如：
101 90 1 4 # 會議101 有90人，使用1點到4點
202 60 3 15 # 會議202 有60人，使用3點到15點

輸出說明：
從所有的會議中，計算出總時長最高，
且人數可被容納的會議安排，並輸出會議總時長。
(注意：時長最長之安排，會議人數不一定合法)


範例輸入 1：
2 4 # 有2間會議室，4場會議要安排
1101 90 # 會議室 1101 可容納90人
2102 60 # 會議室 2102 可容納60人
101 90 1 4 # 會議101 90人 時間為1-4點
102 60 1 3 # 會議102 60人 時間為1-3點
103 60 4 5 # 會議103 60人 時間為4-5點
104 90 1 5 # 會議104 90人 時間為1-5點

此時可安排會議 101, 102, 103
101 安排至 1101，102 安排至 2102，103 安排至 1101，
會議總時長為 3 + 2 + 1 = 6；
或是可安排會議 102, 103, 104；
102 安排至 2102，103 安排至 2102，104 安排至 1101，
會議總時長為 2 + 1 + 4 = 7
時間上也可安排會議 101, 103, 104，會議總時長為 3 + 1 + 4 = 8；
但會議101, 104都必須使用90人的1101會議室，
導致時間衝突(101: 1-4, 104: 1-5)，
故無法安排因此最長會議時數為應該為 7

範例輸出 1：
7

範例輸入 2：
3 6
1101 90
2101 60
3101 30
101 60 1 4
102 60 1 6
103 30 4 9
104 90 6 9
105 60 7 9
106 30 3 7

若每一場會議，不同小時可以被安排在能容納會議人數，不同的會議室，
那就可透過安排103會議的不同小時在不同會議室舉行，來最大化會議時數；
此時會議總時長為22，但103會議的與會者，就需要跑1101, 2101, 3101，3間會議室，為避免讓與會者留下不好的印象，因此公司不希望如此安排。

https://i.imgur.com/lCG7ANN.jpg

因此依照公司政策：每一場會議要安排在能容納會議人數的會議室，且一定要在同一個會議室，最長會議總時為20，安排如下：

https://i.imgur.com/a6LoeDr.jpg


範例輸出 2：
20

輸入 1
1 4
2101 60
104 60 1 5
102 90 1 8
101 60 3 6
103 60 1 6

輸出 1
5

輸入 2
3 6
1101 50
2101 80
3101 40
102 80 1 5
104 60 1 3
103 50 1 3
105 40 5 9
106 60 1 19
101 70 3 4
輸出 2
24

輸入 3
4 4
2103 50
1102 80
3104 60
4105 100
104 50 1 9
103 70 3 7
102 30 2 8
101 60 4 6

輸出 3
20

輸入 4
0 2
101 5 0 2
102 3 22 24

輸出 4
0

輸入 5
2 0
1101 50
2101 80

輸出 5
0

輸入 6
4 4
1101 10
2101 5
3101 15
4101 20
101 30 1 5
103 50 1 5
104 100 3 5
102 25 8 10

輸出 6
0
輸入 7
2 5
2103 50
1102 60
104 50 1 2
102 50 3 4
103 50 5 6
101 50 7 8
106 60 0 23

輸出 7
27

輸入 8
4 10
1101 70
2101 60
3102 80
4103 90
104 50 1 2
102 90 3 4
103 100 5 17
101 70 7 8
105 80 15 24
106 80 0 24
109 60 0 5
108 70 19 24
107 90 1 21
110 80 9 19

輸出 8
56

Answer 1

meeting_room_count = 0
meeting_count = 0
meeting_rooms = []
meetings = []


def input_parameters():
    global meeting_room_count
    global meeting_count
    global meeting_rooms
    global meetings
    raw_parameters = input("Input: ")
    parameters = raw_parameters.split(' ')

    meeting_room_count = int(parameters[0])
    meeting_count = int(parameters[1])

    i = 0
    while i < meeting_room_count:
        raw_meeting_room = input().split(' ')
        meeting_room = [int(raw_meeting_room[0]), int(raw_meeting_room[1])]
        meeting_rooms.append(meeting_room)
        i = i + 1

    j = 0
    while j < meeting_count:
        raw_meeting = input().split(' ')
        meeting = [int(raw_meeting[0]), int(raw_meeting[1]), int(raw_meeting[2]), int(raw_meeting[3])]
        meetings.append(meeting)
        j = j + 1


def process():
    meeting_rooms.sort(key=lambda item: item[1])
    return resolve()


def total_meeting_time(arrangement=None):
    total = 0
    if arrangement is not None:
        for meeting_index in arrangement:
            total += (meetings[meeting_index][3] - meetings[meeting_index][2])

    return total


def get_available_meeting_room(arrangement, meeting):
    occupied_meeting_rooms = []
    if arrangement is not None:
        for meeting_index, meeting_room_index in arrangement.items():
            if meetings[meeting_index][2] < meeting[3] and meetings[meeting_index][3] > meeting[2]:
                occupied_meeting_rooms.append(meeting_room_index)

    available_meeting_rooms = []
    for index in range(meeting_room_count):
        if index in occupied_meeting_rooms:
            continue

        if meeting_rooms[index][1] >= meeting[1]:
            available_meeting_rooms.append(index)

    return available_meeting_rooms


def resolve(init_arrangement=None, init_index=0):
    max_meeting_time = total_meeting_time(init_arrangement)
    index = init_index
    while index < meeting_count:
        if init_arrangement is None:
            arrangement = {}
        else:
            arrangement = init_arrangement.copy()

        available_meeting_rooms = get_available_meeting_room(arrangement, meetings[index])
        if len(available_meeting_rooms) == 0:
            max_meeting_time = max(max_meeting_time, total_meeting_time(arrangement))
        else:
            for available_meeting_room in available_meeting_rooms:
                arrangement[index] = available_meeting_room
                max_meeting_time = max(max_meeting_time, resolve(arrangement, index+1))
        index += 1

    return max_meeting_time

# case sample1(expected result=7):
# meeting_room_count = 2
# meeting_count = 4
# meeting_rooms = [[1101, 90], [2102, 60]]
# meetings = [[101, 90, 1, 4], [102, 60, 1, 3], [103, 60, 4, 5], [104, 90, 1, 5]]

# case sample2(expected result=20):
# meeting_room_count = 3
# meeting_count = 6
# meeting_rooms = [[1101, 90], [2101, 60], [3101, 30]]
# meetings = [[101, 60, 1, 4], [102, 60, 1, 6], [103, 30, 4, 9], [104, 90, 6, 9], [105, 60, 7, 9], [106, 30, 3, 7]]

# case1(expected result=5):
# meeting_room_count = 1
# meeting_count = 4
# meeting_rooms = [[2101, 60]]
# meetings = [[104, 60, 1, 5], [102, 90, 1, 8], [101, 60, 3, 6], [103, 60, 1, 6]]

# case2(expected result=24):
# meeting_room_count = 3
# meeting_count = 6
# meeting_rooms = [[1101, 50], [2101, 80], [3101, 40]]
# meetings = [[102, 80, 1, 5], [104, 60, 1, 3], [103, 50, 1, 3], [105, 40, 5, 9], [106, 60, 1, 19], [101, 70, 3, 4]]

# case3(expected result=20):
# meeting_room_count = 4
# meeting_count = 4
# meeting_rooms = [[2103, 50], [1102, 80], [3104, 60], [4105, 100]]
# meetings = [[104, 50, 1, 9], [103, 70, 3, 7], [102, 30, 2, 8], [101, 60, 4, 6]]

# case4(expected result=0):
# meeting_room_count = 0
# meeting_count = 2
# meetings = [[101, 5, 0, 2], [102, 3, 22, 24]]

# case5(expected result=0):
# meeting_room_count = 2
# meeting_count = 0
# meeting_rooms = [[1101, 50], [2101, 80]]

# case6(expected result=0):
# meeting_room_count = 4
# meeting_count = 4
# meeting_rooms = [[1101, 10], [2101, 5], [3101, 15], [4101, 20]]
# meetings = [[101, 30, 1, 5], [103, 50, 1, 5], [104, 100, 3, 5], [102, 25, 8, 10]]

# case7(expected result=27):
# meeting_room_count = 2
# meeting_count = 5
# meeting_rooms = [[2103, 50], [1102, 60]]
# meetings = [[104, 50, 1, 2], [102, 50, 3, 4], [103, 50, 5, 6], [101, 50, 7, 8], [106, 60, 0, 23]]

# case8(expected result=56):
# meeting_room_count = 4
# meeting_count = 10
# meeting_rooms = [[1101, 70], [2101, 60], [3102, 80], [4103, 90]]
# meetings = [[104, 50, 1, 2], [102, 90, 3, 4], [103, 100, 5, 17], [101, 70, 7, 8], [105, 80, 15, 24], [106, 80, 0, 24], [109, 60, 0, 5], [108, 70, 19, 24], [107, 90, 1, 21], [110, 80, 9, 19]]

input_parameters()

result = process()
print(result)