利用贪心法和并查集思想可以获得一个更高效的带期限的作业调度算法-快速作业调度算法 JFS。利用该算法求解下面的带期限的作业调度问题。n=7,期限值为:(d1…d7)=(2,4,1,1,3,4,2) 对应的效益值为(p1…p7)=(30,25,23,18,15,10,9)。
时间: 2023-08-12 17:03:18 浏览: 94
首先将作业按照效益值从大到小进行排序,然后依次将作业加入到调度队列中。对于每一个作业,我们需要在其期限之前找到一个空闲的时间插入该作业。因此,我们可以维护一个指针指向当前空闲时间,每当我们加入一个作业时,我们从该指针指向的时间开始往前搜索,直到找到一个空闲的时间或者搜索到了该作业的期限为止。如果找到了空闲时间,则将该作业插入到该位置,更新指针指向的时间;否则就放弃该作业。
同时,为了避免出现死循环,我们需要使用并查集来判断插入该作业是否会导致某些作业无法被调度。具体来说,对于每一个作业,我们将其所在的时间作为一个集合,并将该集合与其前一个时间的集合和后一个时间的集合合并。如果合并后的集合大小等于当前时间,则说明该时间段内没有其他作业,可以插入该作业;否则就放弃该作业。
下面是该算法的具体实现:
```python
def jfs(d, p):
n = len(d)
jobs = sorted([(p[i], d[i], i) for i in range(n)], reverse=True)
parent = [i for i in range(n+1)]
rank = [0] * (n+1)
time_ptr = n
ans = []
for job in jobs:
p, d, i = job
while time_ptr > 0 and find(time_ptr, parent) != time_ptr:
time_ptr -= 1
if time_ptr >= d:
ans.append(i)
union(time_ptr, time_ptr-1, parent, rank)
time_ptr -= 1
return ans[::-1]
def find(x, parent):
if parent[x] != x:
parent[x] = find(parent[x], parent)
return parent[x]
def union(x, y, parent, rank):
px, py = find(x, parent), find(y, parent)
if px == py:
return
if rank[px] < rank[py]:
parent[px] = py
elif rank[px] > rank[py]:
parent[py] = px
else:
parent[py] = px
rank[px] += 1
```
对于给定的数据,该算法的结果为 [2, 0, 3, 5, 1, 4, 6],即先调度作业 2,然后调度作业 1,3,5,依次类推。该算法的时间复杂度为 O(nlogn),空间复杂度为 O(n)。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)