go-06-job-scheduler
1.000
Proposed solution
I'll implement a dependency-aware job scheduler according to the requirements.
```go
package challenge
import (
"errors"
"sort"
)
type Job struct {
ID string
Deps []string
Priority int
}
func Schedule(jobs []Job) ([]string, error) {
if len(jobs) == 0 {
return []string{}, nil
}
// Build a map of job ID to job for quick lookup
jobMap := make(map[string]Job)
for _, job := range jobs {
if _, exists := jobMap[job.ID]; exists {
return nil, errors.New("duplicate ID")
}
jobMap[job.ID] = job
}
// Validate dependencies
for _, job := range jobs {
for _, dep := range job.Deps {
if _, exists := jobMap[dep]; !exists {
return nil, errors.New("unknown dependency")
}
}
}
// Build dependency graph and in-degree count
graph := make(map[string][]string) // adjacency list
inDegree := make(map[string]int) // in-degree count
// Initialize all jobs with 0 in-degree
for id := range jobMap {
inDegree[id] = 0
}
// Build the graph and calculate in-degrees
for _, job := range jobs {
for _, dep := range job.Deps {
graph[dep] = append(graph[dep], job.ID)
inDegree[job.ID]++
}
}
// Initialize ready queue with jobs that have no dependencies (in-degree = 0)
ready := make([]Job, 0)
for id, degree := range inDegree {
if degree == 0 {
ready = append(ready, jobMap[id])
}
}
// Sort ready jobs by priority (descending) and then by ID (ascending)
sort.Slice(ready, func(i, j int) bool {
if ready[i].Priority != ready[j].Priority {
return ready[i].Priority > ready[j].Priority // Higher priority first
}
return ready[i].ID < ready[j].ID // Lexicographically smaller ID first
})
result := make([]string, 0)
scheduled := make(map[string]bool)
// Process jobs in topological order
for len(ready) > 0 {
// Pick the job with highest priority and smallest ID
job := ready[0]
ready = ready[1:]
result = append(result, job.ID)
scheduled[job.ID] = true
// Update in-degrees for neighbors
for _, neighbor := range graph[job.ID] {
inDegree[neighbor]--
// If neighbor has no more dependencies, add to ready queue
if inDegree[neighbor] == 0 {
ready = append(ready, jobMap[neighbor])
}
}
// Re-sort ready jobs by priority and ID
sort.Slice(ready, func(i, j int) bool {
if ready[i].Priority != ready[j].Priority {
return ready[i].Priority > ready[j].Priority // Higher priority first
}
return ready[i].ID < ready[j].ID // Lexicographically smaller ID first
})
}
// Check if all jobs were scheduled (detect cycles)
if len(result) != len(jobs) {
return nil, errors.New("cycle detected")
}
return result, nil
}
```Test output (stdout)
run","Package":"challenge","Test":"TestScheduleCycleError"}
{"Time":"2026-06-30T06:26:01.529267822+02:00","Action":"output","Package":"challenge","Test":"TestScheduleCycleError","Output":"=== RUN TestScheduleCycleError\n"}
{"Time":"2026-06-30T06:26:01.529268842+02:00","Action":"output","Package":"challenge","Test":"TestScheduleCycleError","Output":"--- PASS: TestScheduleCycleError (0.00s)\n"}
{"Time":"2026-06-30T06:26:01.529269692+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleCycleError","Elapsed":0}
{"Time":"2026-06-30T06:26:01.529270672+02:00","Action":"run","Package":"challenge","Test":"TestScheduleLongerCycleError"}
{"Time":"2026-06-30T06:26:01.529271452+02:00","Action":"output","Package":"challenge","Test":"TestScheduleLongerCycleError","Output":"=== RUN TestScheduleLongerCycleError\n"}
{"Time":"2026-06-30T06:26:01.529272463+02:00","Action":"output","Package":"challenge","Test":"TestScheduleLongerCycleError","Output":"--- PASS: TestScheduleLongerCycleError (0.00s)\n"}
{"Time":"2026-06-30T06:26:01.529273343+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleLongerCycleError","Elapsed":0}
{"Time":"2026-06-30T06:26:01.529274273+02:00","Action":"run","Package":"challenge","Test":"TestScheduleSelfDependencyError"}
{"Time":"2026-06-30T06:26:01.529274993+02:00","Action":"output","Package":"challenge","Test":"TestScheduleSelfDependencyError","Output":"=== RUN TestScheduleSelfDependencyError\n"}
{"Time":"2026-06-30T06:26:01.529276213+02:00","Action":"output","Package":"challenge","Test":"TestScheduleSelfDependencyError","Output":"--- PASS: TestScheduleSelfDependencyError (0.00s)\n"}
{"Time":"2026-06-30T06:26:01.529277203+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleSelfDependencyError","Elapsed":0}
{"Time":"2026-06-30T06:26:01.529278083+02:00","Action":"run","Package":"challenge","Test":"TestScheduleUnknownDepError"}
{"Time":"2026-06-30T06:26:01.529279103+02:00","Action":"output","Package":"challenge","Test":"TestScheduleUnknownDepError","Output":"=== RUN TestScheduleUnknownDepError\n"}
{"Time":"2026-06-30T06:26:01.529280153+02:00","Action":"output","Package":"challenge","Test":"TestScheduleUnknownDepError","Output":"--- PASS: TestScheduleUnknownDepError (0.00s)\n"}
{"Time":"2026-06-30T06:26:01.529281053+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleUnknownDepError","Elapsed":0}
{"Time":"2026-06-30T06:26:01.529282013+02:00","Action":"run","Package":"challenge","Test":"TestScheduleDuplicateIDError"}
{"Time":"2026-06-30T06:26:01.529282953+02:00","Action":"output","Package":"challenge","Test":"TestScheduleDuplicateIDError","Output":"=== RUN TestScheduleDuplicateIDError\n"}
{"Time":"2026-06-30T06:26:01.529284193+02:00","Action":"output","Package":"challenge","Test":"TestScheduleDuplicateIDError","Output":"--- PASS: TestScheduleDuplicateIDError (0.00s)\n"}
{"Time":"2026-06-30T06:26:01.529285473+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleDuplicateIDError","Elapsed":0}
{"Time":"2026-06-30T06:26:01.529286423+02:00","Action":"run","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder"}
{"Time":"2026-06-30T06:26:01.529287313+02:00","Action":"output","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder","Output":"=== RUN TestScheduleOutputIsValidTopoOrder\n"}
{"Time":"2026-06-30T06:26:01.529290813+02:00","Action":"output","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder","Output":"--- PASS: TestScheduleOutputIsValidTopoOrder (0.00s)\n"}
{"Time":"2026-06-30T06:26:01.529292013+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder","Elapsed":0}
{"Time":"2026-06-30T06:26:01.529292953+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-06-30T06:26:01.529472514+02:00","Action":"output","Package":"challenge","Output":"ok \tchallenge\t0.001s\n"}
{"Time":"2026-06-30T06:26:01.529492044+02:00","Action":"pass","Package":"challenge","Elapsed":0.001}
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.