时间与收益

Description

Given a set of n jobs where each job i has a deadline and profit associated to it. Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit if and only if the job is completed by its deadline. The task is to find the maximum profit and the number of jobs done.

Input

The first line contains an integer T denoting the number of test cases. For each test case, the first line contains two integer n & p denoting the number of houses and number of pipes respectively. Next, p lines contain 3 integer inputs a, b & d, d denoting the diameter of the pipe from the house a to house b.Constraints:1<=T<=50，1<=n<=20，1<=p<=50，1<=a, b<=20，1<=d<=100

Output

For each test case, the output is the number of pairs of tanks and taps installed i.e n followed by n lines that contain three integers: house number of tank, house number of tap and the minimum diameter of pipe between them.

Sample Input

1
9 6
7 4 98
5 9 72
4 6 10
2 8 22
9 7 17
3 1 66

Sample Output

3
2 8 22
3 1 66
5 6 10

思路

贪心

我们可以先看最晚一个任务完成的时间T，从T开始往前推

1. 在T时刻选一个任务ddl大于等于T，且profit最大的任务，完成这个任务，然后从任务列表中移除它
2. 接着在T-1时刻选取任务ddl大于等于T-1，且profix最大的任务...
3. 知道任务列表为空，或者T为0时结束

为什么在T时刻选择ddl大于等于T，profit最大的任务呢？

因为这是最后一个时刻，在这个时刻选择可以完成的价值最大的任务，不会影响到ddl大于等于T的任务，因为它们还可以在T之前的时刻完成，更不会影响到ddl在T之前的任务。所以按时间逆推，选取当前时间可以完成的价值最大的任务。

python(O(tn), t是最晚的时间，n是任务数量)

def solve(tasks):
    times = max([job[1] for job in tasks])
    count, profit = 0, 0
    tasks = set(tasks)
    for t in range(1, times+1)[::-1]:
        cur = None
        # 可以完成的，价值最大的任务
        for task in tasks:
            if task[1] >= t and (not cur or cur[2] < task[2]):
                cur = task
        if cur:
            count += 1
            profit += cur[2]
            tasks.remove(cur)

        if not tasks:
            break
    return count, profit

for _ in range(int(input())):
    input()
    nums = list(map(int, input().split()))
    jobs = [tuple(nums[i:i+3]) for i in range(0, len(nums), 3)]
    print(*solve(jobs))

上面找价值最大的任务时间复杂度是O(n), 使用堆，可以优化成O(logn)

python(O(tlogn))

import heapq, collections
def solve(tasks):
    times = max([job[1] for job in tasks])

    t_tasks = collections.defaultdict(list)
    for task in tasks:
        t_tasks[task[1]].append(task)

    count, profit, q = 0, 0, []
    for t in range(1, times+1)[::-1]:
        for task in t_tasks[t]:
            heapq.heappush(q, -task[2])
        if q:
            count += 1
            profit += -heapq.heappop(q)

    return count, profit


for _ in range(int(input())):
    input()
    nums = list(map(int, input().split()))
    jobs = [tuple(nums[i:i+3]) for i in range(0, len(nums), 3)]
    print(*solve(jobs))