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

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

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

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

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

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

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

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

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

輸出：一個時間表S的n個時間間隔，其中沒有兩個時間間隔在S沖突，總的時間間隔在S是最大的。

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

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

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

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

如果我們想?yún)⒓颖M可能多的活動，我們應該參加在短時間內(nèi)完成的小型活動。參加一個時間跨度較長的活動將不會有好處，因為我們將無法參加其他活動，由于重疊的間隔。盡量先選擇持續(xù)時間最短的項目。

我們?nèi)绾尾拍軐崿F(xiàn)這一目標

選項是將所有間隔存儲在列表中，并根據(jù)結(jié)束時間對列表項進行排序。

初始列表- [（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)在我們將計算程序的間隔。

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("一個人可以參加的最大活動數(shù)是: ", count) 
print("其將參加活動的時間間隔列表為: ", answer)

輸出

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

其他示例

示例1

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

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

# 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，并將變量記為零。計數(shù)和結(jié)束將根據(jù)條件在程序中更改。計數(shù)將告訴我們沒有沖突的最大間隔數(shù)的計數(shù)，結(jié)束將幫助我們跟蹤間隔。我們將在結(jié)果列表中存儲非沖突間隔。

# 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 = []

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

完整代碼：

# 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

在這個例子中，可以清楚地看到，每個前一個間隔的結(jié)束時間等于下一個間隔的開始時間，這意味著我們可以在沒有任何沖突的情況下為每個間隔安排工作，因此結(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

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

在這個例子中，排序后的區(qū)間列表看起來像這樣- [（1，2），（2，3），（2，4），（1，6），（4，9），（5，10）]。我們可以觀察到第1、第2和第5個間隔不重疊，因此不重疊的最大間隔數(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實現(xiàn)區(qū)間調(diào)度算法的文章就介紹到這了,更多相關(guān)Python區(qū)間調(diào)度算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: