Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
package main
import (
"errors"
"fmt"
)
type job struct {
Name string
After []string
}
func main() {
/*
Plan jobs parallel execution:
0
`---- 1 ------------- 4 ------ 7
` | |
`--- 3 | |
` `------- 2 -----/ |
` `------- 5 ------------ /
` `------- 6 ----------- /
`
`--- 8
`------- 9
`------- 10
`------- 11
Expected output (each group means parallel execution):
[[1 3 8] [2 5 6 9 10 11] [4] [7]]
*/
job := []job{
{Name: "1"},
{Name: "2", After: []string{"3"}},
{Name: "3"},
{Name: "4", After: []string{"1", "2"}},
{Name: "5", After: []string{"3"}},
{Name: "6", After: []string{"3"}},
{Name: "7", After: []string{"4", "5", "6"}},
{Name: "8"},
{Name: "9", After: []string{"8"}},
{Name: "10", After: []string{"8"}},
{Name: "11", After: []string{"8"}},
}
result, err := orderJobs(job)
if err != nil {
panic(err)
}
fmt.Printf("%v\n", result)
}
func orderJobs(jobs []job) ([][]string, error) {
var (
result [][]string
done []string
)
for range jobs {
var group []string
for _, j := range jobs {
if contains(done, j.Name) {
continue
}
if len(j.After) == 0 || containsAll(done, j.After) {
group = append(group, j.Name)
}
}
if len(group) == 0 {
break
}
result = append(result, group)
done = append(done, group...)
if len(done) == len(jobs) {
break
}
}
if len(done) != len(jobs) {
return nil, errors.New("cyclic dependency")
}
return result, nil
}
func contains(items []string, find string) bool {
for _, s := range items {
if s == find {
return true
}
}
return false
}
func containsAll(items []string, find []string) bool {
if len(find) == 0 || len(items) == 0 {
return false
}
for _, s := range find {
if !contains(items, s) {
return false
}
}
return true
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment