执行任务赚积分 - 华为OD统一考试(C卷)
OD统一考试(C卷)
分值: 100分
题解: Java / Python / C++
题目描述
现有 N 个任务需要处理,同一时间只能处理一个任务,处理每个任务所需要的时间固定为 1。
每个任务都有最晚处理时间限制和积分值,在最晚处理时间点之前处理完成任务才可获得对应的积分奖励。
可用于处理任务的时间有限,请问在有限的时间内,可获得的最多积分。
输入描述
第一行为一个数 N ,表示有 N 个任务(1 ≤ N ≤ 100 )
第二行为一个数 T ,表示可用于处理任务的时间。(1 ≤ T ≤ 100)
接下来 N 行,每行两个空格分隔的整数(SLA 和 和 V ),SLA 表示任务的最晚处理时间,V 表示任务对应的积分。
1≤SLA≤100 , 0 ≤ V ≤ 100000
输出描述
可获得的最多积分
示例1
输入:
4
3
1 2
1 3
1 4
1 5
输出:
5
说明:
虽然有 3 个单位的时间用于处理任务,可是所有任务在时刻1之后都无效。 所以在第 1 个时间单位内,选择处理有 5 个积分的任务。1−3 时无任务处理。
示例2
输入:
4
3
1 2
1 3
1 4
3 5
输出:
9
说明:
第 1 个时间单位内,处理任务3,获得 4 个积分
第 2 个时间单位内,处理任务 4,获得 5 个积分
第 3 个时间单位内,无任务可处理。
共获得 9 个积分
题解
这道题是一个贪心算法的问题。以下是解题思路:
- 将任务按照最晚处理时间(SLA)升序排序。
- 使用一个最小堆(优先队列)来维护当前可选任务的积分值。
- 遍历排序后的任务列表,将任务的积分值放入最小堆中,并累加总积分。
- 在每一步中,判断优先队里中所有任务能否在(优先队列里中)任务最晚完成时间之内完成,完成不了则将积分值最小的任务删除掉同时维护总积分。
- 最终的总积分即为答案
Java
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), t = scanner.nextInt();
int[][] tasks = new int[n][2];
for (int i = 0; i < n; i++) {
tasks[i][0] = scanner.nextInt();
tasks[i][1] = scanner.nextInt();
}
// 对任务进行排序(时间升序)
Arrays.sort(tasks, Comparator.c
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试真题题解 文章被收录于专栏
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。