任务处理 - 华为OD统一考试(C卷)
OD统一考试(C卷)
分值: 200分
题解: Java / Python / C++
题目描述
在某个项目中有多个任务(用tasks数组表示)需要您进行处理,其中tasks[i]=[si,ei],
你可以在si <= day <= ei 中的任意一天处理该任务,请返回你可以处理的最大任务数
输入描述
第一行为任务数量n,1 <=n<= 100000。
后面n行表示各个任务的开始时间和终止时间,使用si,ei表示,1 <= si <= ei <= 100000
输出描述
输出为一个整数,表示可以处理的最大任务数。
示例1
输入:
3
1 1
1 2
1 3
输出:
3
题解
使用了贪心算法的思想。
主要思路是按照任务的开始时间进行排序,然后使用小根堆(优先队列)来保存当前可以执行的任务的截止时间。
遍历每一天,将当天可以执行的任务加入小根堆,同时弹出已经过期的任务,然后在小根堆中选择距离截止时间最近的任务进行处理。这样可以保证每一天都选择了最优的任务,从而得到最大的任务数。
在代码中,使用了一个**优先队列(小根堆)**来维护当前可以执行的任务的截止时间。具体步骤如下:
- 将任务数组按照开始时间从小到大排序。
- 使用一个小根堆(优先队列)pq,用于保存当前可以执行的任务的截止时间。
- 遍历每一天,将当天开始的任务加入小根堆,同时弹出已经过期的任务。
- 在小根堆中选择距离截止时间最近的任务进行处理,每次处理后将该任务从小根堆中弹出。
- 统计处理的任务数量即为最大任务数。
最后,输出最大任务数即为题目要求的结果。
时间复杂度分析:
假设任务数量为n,排序的时间复杂度为O(nlogn),遍历每一天的时间复杂度为O(100000),而在每一天内对小根堆进行插入和弹出的操作的时间复杂度为O(logn),所以总的时间复杂度为O(nlogn + 100000logn)。由于100000logn相对于nlogn的影响较小,可以近似看作O(nlogn)。
空间复杂度分析:
除了输入和输出所需的空间外,额外使用了一个小根堆来存储任务的截止时间,因此空间复杂度为O(n)。
Java
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] tasks = new int[n][2];
for (int i = 0; i < n; i++) {
tasks[i][0] = in.nextInt();
tasks[i][1] = in.nextInt();
}
Arrays.sort(tasks, (a, b) -> a[0] - b[0]);
// 小根堆,保存当前可以执行的任务的截止时间
PriorityQueue<Integer> pq = new PriorityQueue<>();
int idx = 0, result = 0
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。