(C卷,100分)- 执行任务赚积分（Java & JS & Python & C）

题目描述

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

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

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

输入描述

第一行为一个数 N，表示有 N 个任务

• 1 ≤ N ≤ 100

第二行为一个数 T，表示可用于处理任务的时间

• 1 ≤ T ≤ 100

接下来 N 行，每行两个空格分隔的整数（SLA 和 V），SLA 表示任务的最晚处理时间，V 表示任务对应的积分。

• 1 ≤ SLA ≤ 100
• 0 ≤ V ≤ 100000

输出描述

可获得的最多积分

用例

题目解析

本题类似于

本题解析可以参考上面博客。

另外，本题增加了一个时限T，因为每个任务固定消耗1单位时间，因此时限T单位时间，最多可以完成T个任务。

我们只需要检查最后优先队列中记录的任务数量是否大于T，如果大于T，则将删除超出部分的任务，而被删除的任务都是积分小的。

本题使用到了优先队列，对于Java和Python而言，有内置的优先队列实现类。

而JS和C语言没有，因此我们需要手动实现一个优先队列，关于优先队列的实现可以参考：

LeetCode – 1705 吃苹果的最大数目-CSDN博客 中对于优先队列的解释说明，了解优先队列的底层数据结构，以及上浮、下沉等行为函数

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const n = parseInt(await readline());
  const t = parseInt(await readline());

  const wos = [];
  for (let i = 0; i < n; i++) {
    wos.push((await readline()).split(" ").map(Number));
  }
  console.log(getResult(wos, t));
})();

function getResult(wos, t) {
  // 按照任务截止时间升序
  wos.sort((a, b) => a[0] - b[0]);

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

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

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

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

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

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

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

  return ans;
}

// 基于堆实现优先队列
class PriorityQueue {
  constructor(cpr) {
    this.queue = [];
    this.cpr = cpr;
  }

  swap(a, b) {
    const tmp = this.queue[a];
    this.queue[a] = this.queue[b];
    this.queue[b] = tmp;
  }

  // 上浮
  swim() {
    let c = this.queue.length - 1;

    while (c >= 1) {
      const f = Math.floor((c - 1) / 2);

      if (this.cpr(this.queue[c], this.queue[f]) < 0) {
        this.swap(c, f);
        c = f;
      } else {
        break;
      }
    }
  }

  // 入队
  offer(val) {
    this.queue.push(val);
    this.swim();
  }

  // 下沉
  sink() {
    let f = 0;

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

      let c;
      let val1 = this.queue[c1];
      let val2 = this.queue[c2];
      if (val1 != undefined && val2 != undefined) {
        c = this.cpr(val1, val2) < 0 ? c1 : c2;
      } else if (val1 != undefined) {
        c = c1;
      } else if (val2 != undefined) {
        c = c2;
      } else {
        break;
      }

      if (this.cpr(this.queue[c], this.queue[f]) < 0) {
        this.swap(c, f);
        f = c;
      } else {
        break;
      }
    }
  }

  // 出队
  poll() {
    this.swap(0, this.queue.length - 1);
    const res = this.queue.pop();
    this.sink();
    return res;
  }

  peek() {
    return this.queue[0];
  }

  size() {
    return this.queue.length;
  }
}

Java算法源码

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

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

    int n = sc.nextInt();

    int t = sc.nextInt();

    int[][] wos = new int[n][2];
    for (int i = 0; i < n; i++) {
      wos[i][0] = sc.nextInt();
      wos[i][1] = sc.nextInt();
    }

    System.out.println(getResult(wos, t));
  }

  public static int getResult(int[][] wos, int t) {
    // 按照任务截止时间升序
    Arrays.sort(wos, (a, b) -> a[0] - b[0]);

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

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

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

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

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

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

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

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

    return ans;
  }
}

Python算法源码

import queue

# 输入获取
n = int(input())
t = int(input())
wos = [list(map(int, input().split())) for i in range(n)]


# 算法入口
def getResult():
    # 按照任务截止时间升序
    wos.sort(key=lambda x: x[0])

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

    # ans 记录拿到的积分
    ans = 0
    # curTime 记录当前时间
    curTime = 0

    # 遍历任务
    for wo in wos:
        # 任务截止时间, 任务积分
        endTime, score = wo

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

            # pq中记录的就是curTime之前时刻执行的任务
            if pq.qsize() == 0:
                continue

            # 此时取出pq记录的可执行的任务中最小积分的那个
            min_score = pq.queue[0]

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

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

    return ans


# 算法调用
print(getResult())

C算法源码

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

/* 优先队列实现 */
typedef struct PriorityQueue {
    int *arr;
    int size;

    int (*cmp)(int, int);
} PQ;

PQ *new_PQ(int capacity, int (*cmp)(int, int)) {
    PQ *pq = (PQ *) malloc(sizeof(PQ));
    pq->arr = (int *) malloc(sizeof(int) * capacity);
    pq->size = 0;
    pq->cmp = cmp;
    return pq;
}

void swap_PQ(PQ *pq, int a, int b) {
    int tmp = pq->arr[a];
    pq->arr[a] = pq->arr[b];
    pq->arr[b] = tmp;
}

// 上浮
void swim_PQ(PQ *pq) {
    int c = pq->size - 1;

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

        if (pq->cmp(pq->arr[c], pq->arr[f]) < 0) {
            swap_PQ(pq, c, f);
            c = f;
        } else {
            break;
        }
    }
}

// 入队
void offer_PQ(PQ *pq, int val) {
    pq->arr[pq->size++] = val;
    swim_PQ(pq);
}

// 下沉
void sink_PQ(PQ *pq) {
    int f = 0;

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

        int c;

        if (pq->size > c1 && pq->size > c2) {
            if (pq->cmp(pq->arr[c1], pq->arr[c2]) < 0) {
                c = c1;
            } else {
                c = c2;
            }
        } else if (pq->size > c1 && pq->size <= c2) {
            c = c1;
        } else if (pq->size <= c1 && pq->size > c2) {
            c = c2;
        } else {
            break;
        }

        if (pq->cmp(pq->arr[c], pq->arr[f]) < 0) {
            swap_PQ(pq, c, f);
            f = c;
        } else {
            break;
        }
    }
}

// 出队
int poll_PQ(PQ *pq) {
    swap_PQ(pq, 0, pq->size - 1);
    int res = pq->arr[--pq->size];
    sink_PQ(pq);
    return res;
}

// 获取堆顶元素值
int peek_PQ(PQ *pq) {
    return pq->arr[0];
}

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

int cmp(const void *a, const void *b) {
    int *A = (int*) a;
    int *B = (int*) b;
    return A[0] - B[0];
}

int cmp_PQ(int a, int b) {
    return a - b;
}

int main() {
    int n;
    scanf("%d", &n);

    int t;
    scanf("%d", &t);

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

    // 按照任务截止时间升序
    qsort(wos,  n,sizeof(int *), cmp);

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

    // 当前时间
    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时刻可以指向当前任务
            offer_PQ(pq, score);
            ans += score;
            curTime++;
        } else {
            // 如果 curTime >= 当前任务的截止时间，则当前任务只能在curTime时刻之前找一个时间点执行

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

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

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

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

    printf("%dn", ans);

    return 0;
}