Python-會議安排

Question

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

輸入說明
第一行輸入兩個整數M, N，M是會議室間數(0<=M<=4)，N是申請舉辦會議個數(0<=N<=11)。
其後N行，每一行有三個正整數以空白隔開，代表每一個申請會議的編號、開始時間(0-23)、結束時間(1-24)。
時間以0代表凌晨12點，18代表下午六點，24代表半夜12點。

例如：
1 1 4 #會議1 使用1點到4點
2 3 15 #會議2 使用3點到15點

輸出說明
從所有的申請會議中，計算最長使用總時數，並輸出。

範例輸入：
2 4 # 有2間會議室 4場會議要安排
1 1 3 # 會議1 時間為1-3點
2 1 3 # 會議2 時間為1-3點
3 3 4 # 會議3 時間為3-4點
4 1 5 # 會議4 時間為1-5點

此時可安排會議 1, 2, 3，總時長為 2 + 2 + 1 = 5；
但也可安排會議 1, 3, 4，會議總時長為 2 + 1 + 4 = 7；
或是可安排會議 2, 3, 4，會議總時長為 2 + 1 + 4 = 7；
故最長會議時數為應該為7

範例輸出：
7
Sample input 1
2 5
1 1 4
2 4 10
3 3 9
4 6 15
5 2 10

Sample output 1
20

Sample input 2
4 3
1 1 10
2 5 9
3 2 8

Sample output 2
19

Sample input 3
2 5
1 8 12
2 9 13
3 10 14
4 11 15
5 10 16

Sample output 3
10

Sample input 4
0 1
1 1 2

Sample output 4
0

Sample input 5
1 0

Sample output 5
0

Sample input 6
2 2
1 0 1
2 1 24

Sample output 6
24

Sample input 7
2 4
1 0 5
2 1 5
3 6 15
4 0 1

Sample output 7
19

Sample input 8
1 11
1 0 1
2 1 2
3 2 3
4 3 4
5 4 5
6 5 6
7 6 7
8 7 8
9 8 9
10 9 10
11 10 11

Sample output 8
11

Sample input 9
1 5
1 1 5
2 1 6
3 1 9
4 1 8
5 1 7

Sample output 9
8

Sample input 10
2 8
1 0 6
2 1 6
3 6 15
4 0 1
5 2 6
6 3 6
7 4 6
8 5 6

Sample output 10
21

Answer 1

什么都不需要import的版本

meeting_room_count = 0
meeting_count = 0
meetings = []


def input_parameters():
    global meeting_room_count
    global meeting_count
    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_count:
        raw_meeting = input().split(' ')
        meeting = [int(raw_meeting[0]), int(raw_meeting[1]), int(raw_meeting[2])]
        meetings.append(meeting)
        i = i + 1


def process():
    if meeting_room_count == 0:
        return 0

    return resolve()


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

    return total


def if_clash(arrangement, meeting):
    hour_occupied = dict(zip(range(24), [0 for i in range(24)]))
    if arrangement is not None:
        for index in arrangement:
            current = meetings[index]
            hour = current[1]
            while hour < current[2]:
                count = hour_occupied[hour]
                hour_occupied[hour] = count + 1
                hour += 1
        # print(hour_occupied)

    for hour in range(meeting[1], meeting[2]):
        if hour_occupied[hour] >= meeting_room_count:
            return True

    return False


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()

        if if_clash(arrangement, meetings[index]):
            max_meeting_time = max(max_meeting_time, total_meeting_time(arrangement))
        else:
            arrangement.append(index)
            max_meeting_time = max(max_meeting_time, resolve(arrangement, index+1))
        index += 1

    return max_meeting_time


# case sample(expected result=7):
# meeting_room_count = 2
# meeting_count = 4
# meetings = [[1, 1, 3], [2, 1, 3], [3, 3, 4], [4, 1, 5]]

# case1(expected result=20):
# meeting_room_count = 2
# meeting_count = 5
# meetings = [[1, 1, 4], [2, 4, 10], [3, 3, 9], [4, 6, 15], [5, 2, 10]]

# case2(expected result=19):
# meeting_room_count = 4
# meeting_count = 3
# meetings = [[1, 1, 10], [2, 5, 9], [3, 2, 8]]

# case3(expected result=10):
# meeting_room_count = 2
# meeting_count = 5
# meetings = [[1, 8, 12], [2, 9, 13], [3, 10, 14], [4, 11, 15], [5, 10, 16]]

# case4(expected result=0):
# meeting_room_count = 0
# meeting_count = 1
# meetings = [[1, 1, 2]]

# case5(expected result=0):
# meeting_room_count = 1
# meeting_count = 0
# meetings = []

# case6(expected result=24):
# meeting_room_count = 2
# meeting_count = 2
# meetings = [[1, 0, 1], [2, 1, 24]]

# case7(expected result=19):
# meeting_room_count = 2
# meeting_count = 4
# meetings = [[1, 0, 5], [2, 1, 5], [3, 6, 15], [4, 0, 1]]

# case8(expected result=11):
# meeting_room_count = 1
# meeting_count = 11
# meetings = [[1, 0, 1], [2, 1, 2], [3, 2, 3], [4, 3, 4], [5, 4, 5], [6, 5, 6], [7, 6, 7], [8, 7, 8], [9, 8, 9], [10, 9, 10], [11, 10, 11]]

# case9(expected result=8):
# meeting_room_count = 1
# meeting_count = 5
# meetings = [[1, 1, 5], [2, 1, 6], [3, 1, 9], [4, 1, 8], [5, 1, 7]]

# case10(expected result=21):
# meeting_room_count = 2
# meeting_count = 8
# meetings = [[1, 0, 6], [2, 1, 6], [3, 6, 15], [4, 0, 1], [5, 2, 6], [6, 3, 6], [7, 4, 6], [8, 5, 6]]

input_parameters()

result = process()
print(result)