华为OD真题练习
华为OD机考真题练习
题目描述
任务混部
公司创新实验室正在研究如何最小化资源成本,最大化资源利用率,请你设计算法帮他们解决一个任务混部问题: 有taskNum项任务,
每个任务有开始时间 (startTime ) ,结束时间 (endTime) ,并行度(parallelism)三个属性,
并行度是指这个任务运行时将会占用的服务器数量,一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用,
任务运行完会立即释放(结束时刻不占用)。任务混部问题是指给定一批任务,让这批任务由同一批服务器承载运行,
请你计算完成这批任务混部最少需要多少服务器,从而最大化控制资源成本。
输入描述:
第一行输入为taskNum,表示有taskNum项任务接下来taskNum行,每行三个整数,
表示每个任务的开始时间 (startTime ) ,结束时间(endTime) ,并行度(parallelism)
输出描述:
一个整数,表示最少需要的服务器数量
示例1
输入 3
2 3 1
6 9 2
0 5 1
输出 2
共有三个任务,第一个任务在时间区间[2,3)运行,占用1个服务器,第二个任务在时间区间[6,9)运行,
占用2个服务器,第三个任务在时间区间[0,5)运行,占用1个服务器,
需要最多服务器的时间区间为[2,3)和[6,9),需要2个服务器。
题目分析:
①使用滑动窗口算法破解
解决方案:
【滑动窗口】
typedef struct server {
int val;
int cnt;
} Server;
int cmp(const void *a, const void *b) {
return ((Server *) a)->val - ((Server *) b)->val;
}
int cala(Server *start, Server *end, int n) {
int res = 0;
int cnt = 0;
int i = 0, j = 0;//i,j 表示 begin end的下标
while (i < n && j < n) {
if (start[i].val < end[j].val) {
cnt += start[i].cnt;
i++;
} else {
cnt -= end[j].cnt;
j++;
}
res = cnt < res ? res : cnt;
}
return res;
}
int main() {
int n = 0;
scanf("%d", &n);
Server start[n];
Server end[n];
for (int i = 0; i < n; ++i) {
scanf("%d%d%d", &start[i].val, &end[i].val, &start[i].cnt);
end[i].cnt = start[i].cnt;
}
qsort(start, n, sizeof(Server), cmp);
qsort(end, n, sizeof(Server), cmp);
int num = cala(start, end, n);
printf("%d", num);
return 0;
}