返回目录

题目描述

现有N个任务需要处理，同一时间只能处理一个任务，处理每个任务所需要的时间固定为1。

每个任务都有最晚处理时间限制和积分值，在最晚处理时间点之前处理完成任务才可获得对应的积分奖励。

可用于处理任务的时间有限，请问在有限的时间内，可获得的最多积分。

输入描述：

第一行为一个数N，表示有N个任务，1<=N<=100
第二行为一个数T，表示可用于处理任务的时间。1<=T<=100
接下来N行，每行两个空格分隔的整数（SLA和V），SLA表示任务的最晚处理时间，V表示任务对应的积分。1<=SLA<=100, 0<=V<=100000

输出描述：

可获得的最多积分

示例：

Python算法源码

import heapq

class WorkOrder:
    def __init__(self, end_time, score):
        self.end_time = end_time  # 任务截止时间
        self.score = score  # 任务积分

def main():
    n = int(input())  # 输入任务数量
    t = int(input())  # 输入时间限制
  
    wos = []  # 存储工单的列表
    for _ in range(n):
        end_time, score = map(int, input().split())  # 输入每个工单的截止时间和积分
        wos.append(WorkOrder(end_time, score))  # 将工单信息添加到列表中
  
    wos.sort(key=lambda wo: wo.end_time)  # 按照任务截止时间升序排序
  
    pq = []  # 用于存储积分的优先队列
    cur_time = 0  # 当前时间
    ans = 0  # 已获得的总积分
  
    for wo in wos:
        end_time = wo.end_time  # 当前工单的截止时间
        score = wo.score  # 当前工单的积分
  
        if cur_time < end_time:
            heapq.heappush(pq, score)  # 将当前工单的积分放入优先队列中
            ans += score  # 更新总积分
            cur_time += 1  # 更新当前时间
        else:
            if pq:  # 如果优先队列不为空
                min_score = pq[0]  # 获取当前积分最小的工单积分
                if score > min_score:
                    ans += score - min_score  # 更新总积分，加上替换当前工单后的积分差
                    heapq.heappop(pq)  # 弹出当前积分最小的工单积分
                    heapq.heappush(pq, score)  # 将当前工单的积分放入优先队列中
  
    while len(pq) > t:  # 如果优先队列中的元素数量超过了时间限制
        ans -= heapq.heappop(pq)  # 弹出积分最小的工单积分，并从总积分中减去
  
    print(ans)  # 输出结果

if __name__ == "__main__":
    main()

C算法源码

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int endTime;
    int score;
} WorkOrder;

int compareWorkOrders(const void* a, const void* b) {
    WorkOrder* order1 = (WorkOrder*)a;
    WorkOrder* order2 = (WorkOrder*)b;
    return order1->endTime - order2->endTime;
}

int compareInts(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int getResult(WorkOrder* wos, int n, int t) {
    qsort(wos, n, sizeof(WorkOrder), compareWorkOrders);
    int* scores = (int*)malloc(n * sizeof(int));
    int scoresSize = 0;
    int ans = 0;
    int curTime = 0;

    for (int i = 0; i < n; i++) {
        if (curTime < wos[i].endTime) {
            scores[scoresSize++] = wos[i].score;
            qsort(scores, scoresSize, sizeof(int), compareInts); // Sort to keep the smallest score at the front
            ans += wos[i].score;
            curTime++;
        } else if (scoresSize > 0 && wos[i].score > scores[0]) {
            ans += wos[i].score - scores[0];
            scores[0] = wos[i].score; // Replace the smallest score with the current score
            qsort(scores, scoresSize, sizeof(int), compareInts); // Re-sort
        }
    }

    while (scoresSize > t) {
        ans -= scores[--scoresSize]; // Remove the smallest scores beyond t
    }

    free(scores);
    return ans;
}

int main() {
    int n, t;
    scanf("%d %d", &n, &t);
    WorkOrder* wos = (WorkOrder*)malloc(n * sizeof(WorkOrder));

    for (int i = 0; i < n; i++) {
        scanf("%d %d", &wos[i].endTime, &wos[i].score);
    }

    printf("%d\n", getResult(wos, n, t));
    free(wos);
    return 0;
}

Java算法源码

import java.util.*;

// 工单类
class WorkOrder {
    int endTime; // 任务截止时间
    int score; // 任务积分

    public WorkOrder(int endTime, int score) {
        this.endTime = endTime;
        this.score = score;
    }
}

public class Main {
    // 自定义比较器，用于优先队列
    static Comparator<Integer> cmp = (a, b) -> a - b;

    // 优先队列实现
    static class PriorityQueue {
        List<Integer> arr;
        Comparator<Integer> cmp;

        public PriorityQueue(Comparator<Integer> cmp) {
            this.arr = new ArrayList<>();
            this.cmp = cmp;
        }

        // 上浮
        void swim() {
            int c = arr.size() - 1;

            while (c >= 1) {
                int f = (c - 1) / 2;

                if (cmp.compare(arr.get(c), arr.get(f)) < 0) {
                    Collections.swap(arr, c, f);
                    c = f;
                } else {
                    break;
                }
            }
        }

        // 入队
        void offer(int val) {
            arr.add(val);
            swim();
        }

        // 下沉
        void sink() {
            int f = 0;

            while (true) {
                int c1 = 2 * f + 1;
                int c2 = c1 + 1;

                int c;

                if (arr.size() > c1 && arr.size() > c2) {
                    if (cmp.compare(arr.get(c1), arr.get(c2)) < 0) {
                        c = c1;
                    } else {
                        c = c2;
                    }
                } else if (arr.size() > c1 && arr.size() <= c2) {
                    c = c1;
                } else if (arr.size() <= c1 && arr.size() > c2) {
                    c = c2;
                } else {
                    break;
                }

                if (cmp.compare(arr.get(c), arr.get(f)) < 0) {
                    Collections.swap(arr, c, f);
                    f = c;
                } else {
                    break;
                }
            }
        }

        // 出队
        int poll() {
            Collections.swap(arr, 0, arr.size() - 1);
            int res = arr.remove(arr.size() - 1);
            sink();
            return res;
        }

        // 获取堆顶元素值
        int peek() {
            return arr.get(0);
        }
    }

    // 比较器，用于工单按照截止时间排序
    static Comparator<int[]> comparator = Comparator.comparingInt(a -> a[0]);

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 输入任务数量
        int t = scanner.nextInt(); // 输入时间限制

        int[][] wos = new int[n][2];
        for (int i = 0; i < n; i++) {
            wos[i][0] = scanner.nextInt(); // 输入每个工单的截止时间
            wos[i][1] = scanner.nextInt(); // 输入每个工单的积分
        }

        // 按照任务截止时间升序排序
        Arrays.sort(wos, comparator);

        // pq用于按照积分对任务进行优先级排序，积分越小，优先级越高，目的是为了每次替换掉最少积分的工单
        PriorityQueue pq = new PriorityQueue(cmp);

        // 当前时间
        int curTime = 0;
        // 已获得的积分
        int ans = 0;

        // 遍历任务
        for (int i = 0; i < n; i++) {
            int endTime = wos[i][0]; // 任务截止时间
            int score = wos[i][1]; // 任务积分

            if (curTime < endTime) {
                // 如果 curTime < 当前任务的截止时间，则curTime时刻可以指向当前任务
                pq.offer(score);
                ans += score;
                curTime++;
            } else {
                // 如果 curTime >= 当前任务的截止时间，则当前任务只能在curTime时刻之前找一个时间点执行

                // pq中记录的就是curTime之前时刻执行的任务
                if (pq.arr.size() == 0) continue;

                // 此时取出pq记录的可执行的任务中最小积分的那个
                int minScore = pq.peek();

                // 如果当前任务的积分 > 前面时间内可执行的任务中最小积分
                if (score > minScore) {
                    // 则我们应该将执行pq中最小积分任务的时间，用于执行当前任务，因为这样可以获得更大积分
                    pq.poll();
                    pq.offer(score);
                    ans += score - minScore;
                }
            }
        }

        // 由于时间限制为t单位，而每个任务花费1单位时间，因此最多完成t个任务，对于多出任务应该去除，且优先去除积分少的
        while (pq.arr.size() > t) {
            ans -= pq.poll();
        }

        System.out.println(ans);
    }
}