在Python中安排任务以获取最大利润的程序

问题描述

在实际的工作或生活中，我们往往需要在有限的时间内完成尽可能多的任务，以获取最大的利润。这个问题被称为任务安排问题，是一个经典的计算机科学问题。在这个问题中，我们给定了一组任务，每个任务有一个开始时间和结束时间，我们需要安排这些任务，以尽可能多地完成它们，并获得最大的收益。一个任务可以在其开始时间之后和结束时间之前被完成。

解决方案

在Python中，我们可以使用动态规划的方法来解决这个问题。具体来说，我们可以首先对所有任务按照结束时间进行排序，然后使用一个一维数组来保存截至当前时间点能获取的最大收益。对于每一个任务，我们可以选择将其完成或不完成。如果我们选择将当前任务完成，那么我们就需要找到在当前任务开始之前的、能获取的最大收益，然后加上完成当前任务所获得的收益；如果我们选择不完成当前任务，那么我们就需要使用上一个任务能获取的最大收益。

具体的实现可以参考下面的Python代码：

def schedule(tasks):
    tasks = sorted(tasks, key=lambda x: x[1])
    profits = [0] * len(tasks)
    profits[0] = tasks[0][2]

    for i in range(1, len(tasks)):
        p = tasks[i][2]
        j = i - 1
        while j >= 0 and tasks[j][1] > tasks[i][0]:
            j -= 1
        if j >= 0:
            p += profits[j]
        profits[i] = max(profits[i-1], p)

    return profits[-1]

上述代码中，我们使用了一个元组来表示每个任务，元组的第一个元素为任务开始时间，第二个元素为任务结束时间，第三个元素为完成该任务所获得的收益。任务安排问题的解就是在全部任务中能获得的最大收益。我们可以通过调用上面的 schedule 函数来求解该问题。例如：

tasks = [(0, 3, 2), (1, 3, 4), (2, 5, 7), (4, 6, 1), (4, 7, 4), (6, 8, 3)]
print(schedule(tasks))

上述代码会输出 11，表示在给定的所有任务中能获得的最大收益为 11。

完整代码

下面是完整的代码，其中包括了输入、输出和异常处理：

def schedule(tasks):
    tasks = sorted(tasks, key=lambda x: x[1])
    profits = [0] * len(tasks)
    profits[0] = tasks[0][2]

    for i in range(1, len(tasks)):
        p = tasks[i][2]
        j = i - 1
        while j >= 0 and tasks[j][1] > tasks[i][0]:
            j -= 1
        if j >= 0:
            p += profits[j]
        profits[i] = max(profits[i-1], p)

    return profits[-1]

if __name__ == '__main__':
    try:
        n = int(input())
        tasks = []
        for i in range(n):
            s, e, p = map(int, input().split())
            tasks.append((s, e, p))
        print(schedule(tasks))
    except:
        print("Invalid input.")

下面是一个样例输入和输出：

输入：