資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Go語言程式：求解同時完成所有任務所需的最少資源數
在這篇 Go 語言文章中，我們將學習如何使用區間排程演算法來查詢同時完成所有任務所需的最少資源數。區間排程演算法是一種用於解決排程問題的演算法，其中一組具有開始和結束時間的任務必須安排在有限的資源上。
演算法
步驟 1 − 首先，我們需要匯入 fmt 和 Sort 包。然後初始化所需的結構體和函式。
步驟 2 − task 結構體用於跟蹤任務的開始和結束時間，而 Len() 函式計算 task 結構體的長度。
步驟 3 − 同樣，Swap 和 Less 函式用於交換給定值並查詢提供的較小值。
步驟 4 − 將所需資源數初始化為 1，並將第一個任務的結束時間設定為其結束時間。
步驟 5 − 對於從第二個任務開始的每個任務。如果其開始時間晚於當前結束時間，則遞增所需資源數並將結束時間更新為其結束時間。
步驟 6 − 返回所需資源數。
步驟 7 − 現在，建立 main() 函式。在 main() 中初始化整數陣列並向其儲存值。然後呼叫上面建立的函式並將整數陣列作為引數傳遞給它。
步驟 8 − 現在，將函式返回的結果儲存在一個變數中並在螢幕上列印它。
示例
在這個程式中，我們首先使用 ByEnd 型別和 sort.Sort 函式根據任務的結束時間對任務進行排序。然後，我們將所需資源數初始化為 1，並將第一個任務的結束時間設定為其結束時間。我們迭代其餘的任務，對於每個任務，我們檢查其開始時間是否晚於當前結束時間。如果是，則遞增所需資源數並將結束時間更新為其結束時間。
在 main 函式中，我們建立了一個任務示例列表並使用 minResources 函式列印所需的最少資源數。
package main
import (
"fmt"
"sort"
)
type Task struct {
start int
end int
}
type ByEnd []Task
func (t ByEnd) Len() int {
return len(t)
}
func (t ByEnd) Swap(i, j int) {
t[i], t[j] = t[j], t[i]
}
func (t ByEnd) Less(i, j int) bool {
return t[i].end < t[j].end
}
func minResources(tasks []Task) int {
sort.Sort(ByEnd(tasks))
resources := 1
endTime := tasks[0].end
for i := 1; i < len(tasks); i++ {
if tasks[i].start >= endTime {
resources++
endTime = tasks[i].end
}
}
return resources
}
func main() {
tasks := []Task{{10, 30}, {20, 50}, {40, 17}, {16, 19}, {80, 57}, {75, 76}}
fmt.Println("The given array is:", tasks)
res := minResources(tasks)
fmt.Println("Minimum number of resources needed:", res)
}
輸出
The given array is: [{10 30} {20 50} {40 17} {16 19} {80 57} {75 76}]
Minimum number of resources needed: 4
結論
總而言之，我們已經瞭解瞭如何使用區間排程演算法來確定同時完成一組任務所需的最少資源數。透過根據任務的結束時間對任務進行排序，然後迭代地將資源分配給每個任務，我們可以最大限度地減少所需的總資源數，同時確保每個任務都能按時完成。由於排序操作，該演算法的時間複雜度為 O(n log n)，其中 n 是任務數。
瀏覽量：113
