Python-會議安排

某公司有數間會議室，使用會議前需要各單位登記舉辦會議時間，會議室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

什么都不需要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)

多维数组遍历。为什么用繁体呢，你是台湾的同胞吗？

研究了一下，用递归，遍历所有可能性

# encoding: utf-8
"""
@author: 陈年椰子
@contact: hndm@qq.com
@version: 1.0
@project:test 
@file: meeting_proc.py
@time: 2022-1-5 9:28

说明
輸入說明
第一行輸入兩個整數M, N，M是會議室間數，N是申請舉辦會議個數。
其後N行，每一行有三個正整數以空白隔開，代表每一個申請會議的編號、開始時間、結束時間。時間以0代表凌晨12點，18代表下午六點。
例如：
1 1 4 #會議1 使用1點到4點
2 3 15 #會議2 使用3點到15點

"""
import copy

def init():
    try:
        vals = input("请输入M N(M是會議室間數，N是申請舉辦會議個數)")
        items = vals.split(" ")
        if len(items) == 2:
            return int(items[0]), int(items[1])
    except Exception as e:
        print("Error",repr(e))
        return 0,0

def get_meet():
    try:
        vals = input("请输入會議的  編號 開始時間 結束時間")
        items = vals.split(" ")
        if len(items) == 3:
            return [int(items[0]), int(items[1]), int(items[2])]
    except Exception as e:
        print("Error",repr(e))
        return [0,0,0]






def attend_meet(meet_rooms,meet_list):
    time_total = 0
    if len(meet_list)>0:
        # print('调用', meet_list,  '\t当前会议室安排', meet_rooms)
        meet=meet_list[0]
        m_hours = [n for n in range(meet[1], meet[2])]
        # meet_rooms_save = copy.deepcopy(meet_rooms)
        for room_i in range(len(meet_rooms)):
            # 按会议室按排当前会议
            flag = True
            for m in m_hours:
                if m in meet_rooms[room_i][1]:
                    flag = False
                    # print(meet[0], m_hours, '不能加入', meet_rooms[room_i][1])
                    break
            if flag:
                temp_meet_rooms = copy.deepcopy(meet_rooms)
                temp = temp_meet_rooms[room_i][0]
                temp.append(meet[0])
                temp_meet_rooms[room_i][0] = temp
                temp1 = temp_meet_rooms[room_i][1]
                temp1.extend(m_hours)
                temp_meet_rooms[room_i][1] = temp1
                m_sum = sum([len(m[0]) for m in temp_meet_rooms])
                t_sum = sum([len(m[1]) for m in temp_meet_rooms])
                # if t_sum > time_total:
                #     print(temp_meet_rooms, "合计{}个会议，{}小时".format(m_sum,t_sum))
                # print(meet, '安排去', room_i + 1, '\t会议室安排结果', temp_meet_rooms, "合计{}个会议，{}小时".format(m_sum, t_sum))
                time_total = t_sum if t_sum > time_total else time_total

                # 递归完成下一个会议
                t_sum = attend_meet(temp_meet_rooms[:],meet_list[1:])
                time_total = t_sum if t_sum > time_total else time_total

        else:
            return time_total
    return time_total


def meet_work(M,N,m_list):
    meet_rooms = [[[], []] for n in range(M)]
    max_hours = 0
    for li in range(len(m_list)):
        temp_m_list = copy.deepcopy(m_list[li:] + m_list[:li])
        meets_time = attend_meet(meet_rooms, temp_m_list)
        max_hours = meets_time if meets_time > max_hours else max_hours
    return max_hours



M,N = init()
if M>0 and N>0:
    m_list = []
    while len(m_list)<N:
        m_item = get_meet()
        if m_item != [0,0,0]:
            m_list.append(m_item)
        else:
            print("错误，请重新输入。")
    print(meet_work(M,N,m_list))

除直接遍历外的另一种思路：统计每个小时的会议，如果某个小时的会议安排超过了会议室数量，那么至少要把这个小时对应的会议减少一个。
减少到每个小时的会议安排数都小于会议室数量后，再看哪一种安排方式的总时长最长。

import pandas as pd


def input_parameters():
    raw_parameters = input("Input: ")
    parameters = raw_parameters.split(' ')
    meeting_room_count = int(parameters[0])
    meeting_count = int(parameters[1])

    df = pd.DataFrame(columns=['num', 'start', 'end'])

    i = 0
    while i < meeting_count:
        raw_meeting = input()
        meeting = raw_meeting.split(' ')
        df.loc[i] = meeting
        df['start'] = df['start'].astype('int')
        df['end'] = df['end'].astype('int')
        i = i + 1

    return meeting_room_count, meeting_count, df


def process(meeting_room_count, meeting_count, meetings):
    meetings['total'] = meetings['end'] - meetings['start']
    if meeting_count <= meeting_room_count:
        return meetings['total'].sum()

    hour_conflict = if_occupied(meeting_room_count, meetings)

    lost_hour = 0
    if len(hour_conflict) > 0:
        meetings['conflict_hour'] = ''
        meetings['rate'] = 0
        meetings['checked'] = False
        for index, row in meetings.iterrows():
            current_hour_conflict = [hour for hour in hour_conflict if hour in range(row['start'], row['end'])]
            meetings.loc[index, 'conflict_hour'] = ','.join(str(hour) for hour in current_hour_conflict)
            meetings.loc[index, 'rate'] = len(current_hour_conflict) / len(hour_conflict)
        lost_hour = resolve(meeting_room_count, meetings)

    return meetings['total'].sum() - lost_hour


def if_occupied(meeting_room_count, meetings):
    hour_occupied = dict(zip(range(24), [0 for i in range(24)]))
    for index, row in meetings.iterrows():
        hour = row['start']
        while hour < row['end']:
            count = hour_occupied[hour]
            hour_occupied[hour] = count + 1
            hour += 1
    # print(hour_occupied)

    hour_conflict = []
    for key, value in hour_occupied.items():
        if value > meeting_room_count:
            hour_conflict.append(key)
    # print(hour_conflict)

    return hour_conflict


def resolve(meeting_room_count, meetings):
    min_lost_hour = meetings['total'].sum()
    sorted_meetings = meetings.sort_values(by = ['rate', 'total'], ascending = [False, True])
    for index, row in sorted_meetings.iterrows():
        if row['checked']:
            continue

        if row['rate'] <= 0:
            break

        sorted_meetings.loc[index, 'checked'] = True
        current_lost_hour = row['total']
        current_meetings = sorted_meetings.drop([index])
        current_hour_conflict = if_occupied(meeting_room_count, current_meetings)

        if len(current_hour_conflict) > 0:
            for index, row in current_meetings.iterrows():
                meeting_hour_conflict = [hour for hour in current_hour_conflict if hour in range(row['start'], row['end'])]
                current_meetings.loc[index, 'conflict_hour'] = ','.join(str(hour) for hour in meeting_hour_conflict)
                current_meetings.loc[index, 'rate'] = len(meeting_hour_conflict) / len(current_hour_conflict)
            min_lost_hour = min(min_lost_hour, current_lost_hour + resolve(meeting_room_count, current_meetings))
        else:
            min_lost_hour = min(min_lost_hour, current_lost_hour)

    return min_lost_hour

#case sample:
# meeting_room_count = 2
# meeting_count = 4
# meetings = pd.DataFrame({'num': [1, 2, 3, 4], 'start': [1, 1, 3, 1], 'end': [3, 3, 4, 5]})

#case1
# meeting_room_count = 2
# meeting_count = 5
# meetings = pd.DataFrame({'num': [1, 2, 3, 4, 5], 'start': [1, 4, 3, 6, 2], 'end': [4, 10, 9, 15, 10]})

#case2
# meeting_room_count = 4
# meeting_count = 3
# meetings = pd.DataFrame({'num': [1, 2, 3], 'start': [1, 5, 2], 'end': [10, 9, 8]})

#case3
# meeting_room_count = 2
# meeting_count = 5
# meetings = pd.DataFrame({'num': [1, 2, 3, 4, 5], 'start': [8, 9, 10, 11, 10], 'end': [12, 13, 14, 15, 16]})

meeting_room_count, meeting_count, meetings = input_parameters()

result = process(meeting_room_count, meeting_count, meetings)
print(result)

针对那个问题，做下修改， 改成时长优先。

import copy


def init():
    try:
        vals = input("请输入M N(M是會議室間數，N是申請舉辦會議個數)")
        items = vals.split(" ")
        if len(items) == 2:
            return int(items[0]), int(items[1])
    except Exception as e:
        print("Error", repr(e))
        return 0, 0


def get_meet():
    try:
        vals = input("请输入會議的  編號 開始時間 結束時間")
        items = vals.split(" ")
        if len(items) == 3:
            return [int(items[0]), int(items[1]), int(items[2])]
    except Exception as e:
        print("Error", repr(e))
        return [0, 0, 0]


def attend_meet(meet_rooms, meet_list):
    time_total = 0
    if len(meet_list) > 0:
        # print('调用', meet_list,  '\t当前会议室安排', meet_rooms)
        meet = meet_list[0]
        m_hours = [n for n in range(meet[1], meet[2])]
        # meet_rooms_save = copy.deepcopy(meet_rooms)
        for room_i in range(len(meet_rooms)):
            # 按会议室按排当前会议
            flag = True
            for m in m_hours:
                if m in meet_rooms[room_i][1]:
                    flag = False
                    print(meet[0], m_hours, '不能加入', meet_rooms[room_i][1],"当前安排",meet_rooms)
                    break
            if flag:
                temp_meet_rooms = copy.deepcopy(meet_rooms)
                temp = temp_meet_rooms[room_i][0]
                temp.append(meet[0])
                temp_meet_rooms[room_i][0] = temp
                temp1 = temp_meet_rooms[room_i][1]
                temp1.extend(m_hours)
                temp_meet_rooms[room_i][1] = temp1
                m_sum = sum([len(m[0]) for m in temp_meet_rooms])
                t_sum = sum([len(m[1]) for m in temp_meet_rooms])
                print(meet, '安排去', room_i + 1, '\t会议室安排结果', temp_meet_rooms, "合计{}个会议，{}小时".format(m_sum, t_sum))
                if t_sum > time_total:
                    print(temp_meet_rooms, "合计{}个会议，{}小时".format(m_sum,t_sum))

                time_total = t_sum if t_sum > time_total else time_total

                # 递归完成下一个会议
                t_sum = attend_meet(temp_meet_rooms[:], meet_list[1:])
                time_total = t_sum if t_sum > time_total else time_total

        else:
            return time_total
    return time_total


def meet_work(M, N, m_list):
    meet_rooms = [[[], []] for n in range(M)]
    max_hours = 0
    for li in range(len(m_list)):
        temp_m_list = copy.deepcopy(m_list[li:] + m_list[:li])
        temp_m_list = sorted(temp_m_list, key=lambda x: x[2] - x[1])
        temp_m_list.reverse()
        meets_time = attend_meet(meet_rooms, temp_m_list)
        max_hours = meets_time if meets_time > max_hours else max_hours
    return max_hours


M, N = init()
if M > 0 and N > 0:
    m_list = []
    while len(m_list) < N:
        m_item = get_meet()
        if m_item != [0, 0, 0]:
            m_list.append(m_item)
        else:
            print("错误，请重新输入。")
    print(meet_work(M, N, m_list))