公司创新实验室正在研究如何最小化资源成本,最大化资源利用率,请你设计算法帮他们 (startTime ),结束时间(endTime),并行度(parallelism)三个属性,并行度是指这个任务运行时将 接下来 taskNum 行,每行三个整数,表示每个任务的开始时间 会占用的服务器数量,一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用 ,任务运行完会立即释放(结束时刻不占用)。任务混部问题是指给定一批任务,让这批 任务由同一批服务器承载运行,请你计算完成这批任务混部最少需要多少服务器,从而最 大化控制资源成本。
时间: 2023-11-20 17:06:50 浏览: 54
这个问题可以使用贪心算法来解决。具体地,我们首先将所有任务按照开始时间从小到大排序,然后对于每个任务,尽可能地将它分配给之前没有被占用的服务器。如果没有可用的服务器,则需要启用一个新的服务器来运行该任务。同时,我们需要记录每个服务器的结束时间,以便在之后的任务中能够找到可用的服务器。
以下是该算法的伪代码:
```
sort(tasks) // 按照开始时间排序
servers = [] // 用于记录每个服务器的结束时间
for task in tasks:
assigned = False
for i, end_time in enumerate(servers):
if end_time <= task.start_time:
servers[i] = task.end_time
assigned = True
break
if not assigned:
servers.append(task.end_time)
print(len(servers)) // 输出服务器数量
```
该算法的时间复杂度是 O(nlogn),其中 n 是任务数量。
相关问题
有 tasknum 项任务,每个任务有开始时间(starttime ),结束时间(endtime),并行度(pa
并行度(parallelism)是指在同一时间内可以同时进行的任务数量。对于给定的 tasknum 项任务,每个任务有开始时间 starttime 和结束时间 endtime ,要确定并行度,需要考虑以下几个因素:
1. 始终同时进行的任务数量:
如果给定的任务的开始时间和结束时间没有交叉,那么这些任务可以同时进行。这意味着并行度等于 tasknum。
2. 存在时间重叠的任务:
如果给定的任务之间存在时间重叠,即存在一些任务的结束时间晚于其他任务的开始时间,则这些任务不能同时进行。在这种情况下,需要确定最大的并行度。
为了确定最大并行度,可以按照开始时间排序所有任务。然后从第一个任务开始,计算当前同时进行的任务数量,直到当前任务的结束时间。在这个过程中,记录并更新记录最大并行度的变量。然后重复这个过程,直到遍历完所有的任务。
最终,记录的最大并行度将是符合要求的并行度。
对象集合,对象属性有 startTime持仓开始时间,endTime持仓结束时间,对象包含的持仓时间有交集,用Java代码求总的持仓时间
可以使用以下代码求总的持仓时间:
```java
public static long getTotalHoldingTime(List<Position> positions) {
long totalHoldingTime = 0;
if (positions == null || positions.size() == 0) {
return totalHoldingTime;
}
// 按照持仓开始时间排序
Collections.sort(positions, Comparator.comparing(Position::getStartTime));
Position currPosition = positions.get(0);
for (int i = 1; i < positions.size(); i++) {
Position nextPosition = positions.get(i);
if (nextPosition.getStartTime() < currPosition.getEndTime()) {
// 如果下一个持仓的开始时间早于当前持仓的结束时间,说明存在交集
// 更新当前持仓的结束时间为下一个持仓的结束时间
currPosition.setEndTime(Math.max(currPosition.getEndTime(), nextPosition.getEndTime()));
} else {
// 否则,将当前持仓时间累加到总的持仓时间中,并更新当前持仓为下一个持仓
totalHoldingTime += currPosition.getEndTime() - currPosition.getStartTime();
currPosition = nextPosition;
}
}
// 最后一个持仓也要累加到总的持仓时间中
totalHoldingTime += currPosition.getEndTime() - currPosition.getStartTime();
return totalHoldingTime;
}
class Position {
private long startTime;
private long endTime;
public Position(long startTime, long endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
public long getStartTime() {
return startTime;
}
public void setStartTime(long startTime) {
this.startTime = startTime;
}
public long getEndTime() {
return endTime;
}
public void setEndTime(long endTime) {
this.endTime = endTime;
}
}
```
其中,`getTotalHoldingTime`方法接收一个持仓的列表,按照持仓开始时间排序,然后遍历列表中的所有持仓,如果发现当前持仓和下一个持仓存在交集,则更新当前持仓的结束时间为下一个持仓的结束时间;否则,将当前持仓时间累加到总的持仓时间中,并更新当前持仓为下一个持仓。最后,将最后一个持仓的时间也累加到总的持仓时间中,并返回总的持仓时间。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)