Python實(shí)現(xiàn)區(qū)間調(diào)度算法

更新時(shí)間：2024年10月28日 09:06:28 作者：python收藏家

區(qū)間調(diào)度算法是一種在給定的一組任務(wù)中,選擇盡可能多的相互不沖突的任務(wù)的算法,本文主要介紹了如何使用Python實(shí)現(xiàn)區(qū)間調(diào)度算法,有需要的可以參考下

什么是區(qū)間調(diào)度算法

在算法設(shè)計(jì)領(lǐng)域，區(qū)間排序是一類(lèi)問(wèn)題。這些計(jì)劃考慮到了一些任務(wù)。每個(gè)任務(wù)都由一個(gè)時(shí)間間隔表示，該時(shí)間間隔指示機(jī)器完成該任務(wù)所需的時(shí)間。如果系統(tǒng)或資源上的任何兩個(gè)時(shí)間間隔之間沒(méi)有重疊，則時(shí)間間隔的子集是兼容的。

區(qū)間調(diào)度算法的核心思想是將任務(wù)的開(kāi)始和結(jié)束時(shí)間分開(kāi)考慮，通過(guò)比較任務(wù)的開(kāi)始時(shí)間或結(jié)束時(shí)間來(lái)確定任務(wù)的執(zhí)行順序。具體來(lái)說(shuō)，可以將任務(wù)按照開(kāi)始時(shí)間或結(jié)束時(shí)間進(jìn)行排序，然后根據(jù)排序結(jié)果逐個(gè)執(zhí)行任務(wù)，同時(shí)記錄當(dāng)前已執(zhí)行的任務(wù)集合，以便在需要時(shí)進(jìn)行調(diào)整。

區(qū)間調(diào)度最大化問(wèn)題的目標(biāo)是確定最大的兼容集或具有最小可能重疊的區(qū)間集合。這個(gè)想法是通過(guò)完成盡可能多的任務(wù)來(lái)優(yōu)化吞吐量。

區(qū)間調(diào)度問(wèn)題：

輸入： n個(gè)間隔{s（i），.，f（i）−1}的輸入，其中1 ≤ i ≤ n，i表示間隔，s（i）表示開(kāi)始時(shí)間，f（i）表示結(jié)束時(shí)間。

輸出：一個(gè)時(shí)間表S的n個(gè)時(shí)間間隔，其中沒(méi)有兩個(gè)時(shí)間間隔在S沖突，總的時(shí)間間隔在S是最大的。

假設(shè)我們有一個(gè)事件列表，每個(gè)事件的格式為[a，b]，其中a是開(kāi)始時(shí)間，b是結(jié)束時(shí)間。一個(gè)人一次只能參加其中一個(gè)活動(dòng)，他們可以立即從一個(gè)活動(dòng)轉(zhuǎn)到另一個(gè)活動(dòng)。如果兩個(gè)事件的停止時(shí)間和開(kāi)始時(shí)間分別重合。找到一個(gè)人可以參加的最大數(shù)量的活動(dòng)。

intervals = [[4，5]，[0，2]，[2，7]，[1，3]，[0，4]]

在這個(gè)問(wèn)題中，我們必須確定一個(gè)人可以參加的活動(dòng)的最大數(shù)量。檢查下面的圖表，看看這個(gè)人是如何盡可能多地參加活動(dòng)的。

考慮下面的場(chǎng)景，如果一個(gè)人在間隔（4，5）和（0，2）參加一個(gè)事件，他將無(wú)法在間隔（2，7）、（1，3）和（0，4）參加事件，因此事件的最大數(shù)量將是兩個(gè)。

如果我們想?yún)⒓颖M可能多的活動(dòng)，我們應(yīng)該參加在短時(shí)間內(nèi)完成的小型活動(dòng)。參加一個(gè)時(shí)間跨度較長(zhǎng)的活動(dòng)將不會(huì)有好處，因?yàn)槲覀儗o(wú)法參加其他活動(dòng)，由于重疊的間隔。盡量先選擇持續(xù)時(shí)間最短的項(xiàng)目。

我們?nèi)绾尾拍軐?shí)現(xiàn)這一目標(biāo)

選項(xiàng)是將所有間隔存儲(chǔ)在列表中，并根據(jù)結(jié)束時(shí)間對(duì)列表項(xiàng)進(jìn)行排序。

初始列表- [（4，5），（0，2），（2，7），（1，3），（0，4）]
排序列表- [（0，2），（1，3），（0，4），（4，5），（2，7）]

排序后的圖如下所示：

根據(jù)圖，我們可以參加（0，2）和（4，5）事件，但其余的仍然重疊?，F(xiàn)在我們將計(jì)算程序的間隔。

intervals = [(4, 5), (0, 2), (2, 7), (1, 3), (0, 4)] 

# sorting the intervals 
intervals.sort(key=lambda x: x[1]) 

# print(intervals) 
# counting the events 
count = 0
# keeping track of ending of intervals 
end = 0
# list of the intervals in which person will attend the events 
answer = [] 

# traversing the list of intervals 
for interval in intervals: 
	# starting time of next interval will >= ending 
	# time of previous interval 
	if(end <= interval[0]): 
		# update the and 
		end = interval[1] 
		# increment the count by one 
		count += 1
		# insert the non-conflict interval in the list 
		answer.append(interval) 

# print statements will print non-conflict 
# intervals count as well intervals 
print("一個(gè)人可以參加的最大活動(dòng)數(shù)是: ", count) 
print("其將參加活動(dòng)的時(shí)間間隔列表為: ", answer)

輸出

'一個(gè)人可以參加的最大活動(dòng)數(shù)是：', 2
'其將參加活動(dòng)的時(shí)間間隔列表為：', [(0, 2), (4, 5)]

其他示例

示例1

# list of intervals 
intervals = [(1, 3), (7, 12), (2, 5), (6, 18), (14, 16)]

接著，我們根據(jù)每個(gè)元組的結(jié)束時(shí)間或第二個(gè)元素對(duì)元組列表進(jìn)行排序。Lambda是一個(gè)小函數(shù)，允許你傳遞任意數(shù)量的參數(shù)，但表達(dá)式應(yīng)該在一行中。在上述情況下，lambda函數(shù)訪問(wèn)interval列表中元組的第二個(gè)元素，并將其作為鍵傳遞給sort函數(shù)，以便元組將按照第二個(gè)元素以升序排序。

# list of intervals 
intervals = [(1,3),(7,12),(2,5),(6,18),(14,16)] 

# sorting the intervals 
intervals.sort(key = lambda x : x [1]) 
print(intervals)

輸出

[(1, 3), (2, 5), (7, 12), (14, 16), (6, 18)]

現(xiàn)在我們初始化count，并將變量記為零。計(jì)數(shù)和結(jié)束將根據(jù)條件在程序中更改。計(jì)數(shù)將告訴我們沒(méi)有沖突的最大間隔數(shù)的計(jì)數(shù)，結(jié)束將幫助我們跟蹤間隔。我們將在結(jié)果列表中存儲(chǔ)非沖突間隔。

# counting the events 
count = 0

# keeping track of ending of intervals 
end = 0

# list of the intervals in which person will attend the events 
answer = []

我們逐個(gè)遍歷每個(gè)間隔，并檢查下一個(gè)間隔的開(kāi)始時(shí)間是否大于或等于前一個(gè)間隔的結(jié)束時(shí)間。如果為真，我們將計(jì)數(shù)器遞增1并將該間隔插入到答案列表中，我們這樣做是因?yàn)椴粦?yīng)該有任何沖突，并且因?yàn)槲覀円呀?jīng)基于間隔的結(jié)束時(shí)間對(duì)間隔進(jìn)行了排序，所以我們首先參加排序周期間隔，以便我們可以最大化結(jié)果。在最后，我們只是打印計(jì)數(shù)的非沖突的時(shí)間間隔以及非沖突的時(shí)間間隔作為一個(gè)列表。

完整代碼：

# list of intervals 
intervals = [(1, 3), (7, 12), (2, 5), (6, 18), (14, 16)] 

# sorting the intervals 
intervals.sort(key=lambda x: x[1]) 
# print(intervals) 

# counting the events 
count = 0

# keeping track of ending of intervals 
end = 0

# list of the intervals in which person will attend the events 
answer = [] 

# traversing the list of intervals 
for interval in intervals: 

	# starting time of next interval will >= ending time of previous interval 
	if(end <= interval[0]): 

		# update the and 
		end = interval[1] 

		# increment the count by one 
		count += 1

		# insert the non-conflict interval in the list 
		answer.append(interval) 

# print statements will print non-conflict intervals count as well intervals 
print("The count of Non-conflict intervals : ", count) 
print("List of the intervals : ", answer)

輸出

'The count of Non-conflict intervals : ', 3
'List of the intervals : ', [(1, 3), (7, 12), (14, 16)]

示例2

在這個(gè)例子中，可以清楚地看到，每個(gè)前一個(gè)間隔的結(jié)束時(shí)間等于下一個(gè)間隔的開(kāi)始時(shí)間，這意味著我們可以在沒(méi)有任何沖突的情況下為每個(gè)間隔安排工作，因此結(jié)果將是間隔的數(shù)量，即5。

intervals = [(2, 5), (5, 10), (10, 20), (20, 30), (30, 45)] 

# sorting the intervals 
intervals.sort(key=lambda x: x[1]) 
print(intervals) 
# counting the events 
count = 0
# keeping track of ending of intervals 
end = 0
# list of the intervals in which person will attend the events 
answer = [] 
# traversing the list of intervals 
for interval in intervals: 
	# starting time of next interval will >= ending time of previous interval 
	if(end <= interval[0]): 
		# update the and 
		end = interval[1] 
		# increment the count by one 
		count += 1
		# insert the non-conflict interval in the list 
		answer.append(interval) 

# print statements will print non-conflict intervals count as well intervals 
print("The count of non-overlapping events : ", count) 
print("List of intervals without overlapping : ", answer)

輸出

[(2, 5), (5, 10), (10, 20), (20, 30), (30, 45)]
'The count of non-overlapping events : ', 5
'List of intervals without overlapping : ', [(2, 5), (5, 10), (10, 20), (20, 30), (30, 45)]

示例3

在這個(gè)例子中，間隔不符合我們的要求，所以間隔將以這樣的方式排序，即最小周期間隔將開(kāi)始，然后是更大的間隔。這就是排序后的區(qū)間- [（3，5），（4，5），（6，8），（10，11），（2，12），（9，12），（11，12）]。正如你所看到的，第一、第三、第四和第七個(gè)間隔彼此不重疊，所以沒(méi)有沖突的間隔的最大數(shù)量將是4。

intervals = [(2, 12), (3, 5), (4, 5), (6, 8), (9, 12), (10, 11), (11, 12)] 

# sorting the intervals 
intervals.sort(key=lambda x: x[1]) 
print(intervals) 
# counting the events 
count = 0
# keeping track of ending of intervals 
end = 0
# list of the intervals in which person will attend the events 
answer = [] 

# traversing the list of intervals 
for interval in intervals: 
	# starting time of next interval will >= ending time of previous interval 
	if(end <= interval[0]): 
		# update the and 
		end = interval[1] 
		# increment the count by one 
		count += 1
		# insert the non-conflict interval in the list 
		answer.append(interval) 

# print statements will print non-conflict intervals count as well intervals 
print("The count of non-overlapping events : ", count) 
print("List of intervals without overlapping : ", answer)

輸出

[(3, 5), (4, 5), (6, 8), (10, 11), (2, 12), (9, 12), (11, 12)]
'The count of non-overlapping events : ', 4
'List of intervals without overlapping : ', [(3, 5), (6, 8), (10, 11), (11, 12)]

示例4

在這個(gè)例子中，排序后的區(qū)間列表看起來(lái)像這樣- [（1，2），（2，3），（2，4），（1，6），（4，9），（5，10）]。我們可以觀察到第1、第2和第5個(gè)間隔不重疊，因此不重疊的最大間隔數(shù)為3。

intervals = [(1, 6), (2, 3), (5, 10), (1, 2), (2, 4), (4, 9)] 

# sorting the intervals 
intervals.sort(key=lambda x: x[1]) 
print(intervals) 
# counting the events 
count = 0
# keeping track of ending of intervals 
end = 0
# list of the intervals in which person will attend the events 
answer = [] 

# traversing the list of intervals 
for interval in intervals: 
	# starting time of next interval will >= ending time of previous interval 
	if(end <= interval[0]): 
		# update the and 
		end = interval[1] 
		# increment the count by one 
		count += 1
		# insert the non-conflict interval in the list 
		answer.append(interval) 

# print statements will print non-conflict intervals count as well intervals 
print("The count of non-overlapping events : ", count) 
print("List of intervals without overlapping : ", answer)

輸出

[(1, 2), (2, 3), (2, 4), (1, 6), (4, 9), (5, 10)]
'The count of non-overlapping events : ', 3
'List of intervals without overlapping : ', [(1, 2), (2, 3), (4, 9)]

到此這篇關(guān)于Python實(shí)現(xiàn)區(qū)間調(diào)度算法的文章就介紹到這了,更多相關(guān)Python區(qū)間調(diào)度算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: