go-06-job-scheduler

# Dependency-aware job scheduler

Implement a file **`solution.go`** in `package challenge` exporting:

```go
type Job struct {
    ID       string
    Deps     []string
    Priority int
}

func Schedule(jobs []Job) ([]string, error)
```

`Schedule` computes a valid execution order for `jobs` and returns the slice of
job IDs in that order. The order is a **topological order**: a job may appear in
the output only after every ID in its `Deps` has already appeared earlier.

## Selection rule (deterministic)

Many topological orders may exist; this challenge fixes a single one. Build the
output by repeating the following step until every job is scheduled:

1. Consider the set of **ready** jobs: not-yet-scheduled jobs whose dependencies
   are *all* already scheduled.
2. Among the ready jobs, pick the one with the **highest `Priority`**.
3. Break ties (equal `Priority`) by the **lexicographically smallest `ID`**
   (Go string `<`).
4. Append the chosen job's ID to the output, mark it scheduled, and repeat.

This makes the result unique and fully determined by the input.

## Rules

- The output is a slice of job IDs (`[]string`). Every job appears exactly once.
- An **empty input** (`nil` or `len 0`) returns an empty (`len 0`) slice and a
  `nil` error.
- Return a non-nil error and a `nil`/empty slice when any of these hold:
  - **Duplicate ID** — two jobs share the same `ID`.
  - **Unknown dependency** — some job's `Deps` references an ID that is not the
    `ID` of any job in `jobs`.
  - **Cycle** — the dependencies form a cycle, so some jobs can never become
    ready. A self-dependency (`a` depends on `a`) is a cycle.
- Duplicate entries inside a single job's `Deps` are allowed and harmless: the
  dependency just needs to be satisfied once.

## Examples

Linear chain — `c` depends on `b`, `b` depends on `a`:

```go
Schedule([]Job{
    {ID: "c", Deps: []string{"b"}},
    {ID: "b", Deps: []string{"a"}},
    {ID: "a"},
})
// → ["a", "b", "c"], nil
```

Priority tie-break — `a` and `b` are both ready immediately; `b` has the higher
priority, so it runs first:

```go
Schedule([]Job{
    {ID: "a", Priority: 1},
    {ID: "b", Priority: 5},
})
// → ["b", "a"], nil
```

ID tie-break — equal priorities, so the smaller ID wins:

```go
Schedule([]Job{
    {ID: "y", Priority: 0},
    {ID: "x", Priority: 0},
})
// → ["x", "y"], nil
```

Diamond — `d` depends on both `b` and `c`, which both depend on `a`. With equal
priorities the smaller ID breaks the `b`/`c` tie:

```go
Schedule([]Job{
    {ID: "a"},
    {ID: "b", Deps: []string{"a"}},
    {ID: "c", Deps: []string{"a"}},
    {ID: "d", Deps: []string{"b", "c"}},
})
// → ["a", "b", "c", "d"], nil
```

Cycle — returns an error:

```go
Schedule([]Job{
    {ID: "a", Deps: []string{"b"}},
    {ID: "b", Deps: []string{"a"}},
})
// → nil, <error>
```

Use only the Go standard library.

package challenge

import (
	"reflect"
	"testing"
)

func TestScheduleEmpty(t *testing.T) {
	got, err := Schedule(nil)
	if err != nil {
		t.Fatalf("Schedule(nil) error = %v, want nil", err)
	}
	if len(got) != 0 {
		t.Fatalf("Schedule(nil) = %v, want empty slice", got)
	}

	got, err = Schedule([]Job{})
	if err != nil {
		t.Fatalf("Schedule([]) error = %v, want nil", err)
	}
	if len(got) != 0 {
		t.Fatalf("Schedule([]) = %v, want empty slice", got)
	}
}

func TestScheduleSingle(t *testing.T) {
	got, err := Schedule([]Job{{ID: "only"}})
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	if want := []string{"only"}; !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestScheduleLinearChain(t *testing.T) {
	jobs := []Job{
		{ID: "c", Deps: []string{"b"}},
		{ID: "b", Deps: []string{"a"}},
		{ID: "a"},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	if want := []string{"a", "b", "c"}; !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestScheduleDiamond(t *testing.T) {
	jobs := []Job{
		{ID: "d", Deps: []string{"b", "c"}},
		{ID: "b", Deps: []string{"a"}},
		{ID: "c", Deps: []string{"a"}},
		{ID: "a"},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	// Equal priorities: a first, then b<c by ID, then d.
	if want := []string{"a", "b", "c", "d"}; !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestSchedulePriorityTieBreak(t *testing.T) {
	jobs := []Job{
		{ID: "a", Priority: 1},
		{ID: "b", Priority: 5},
		{ID: "c", Priority: 3},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	// All ready; ordered by descending priority: b(5), c(3), a(1).
	if want := []string{"b", "c", "a"}; !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestScheduleSmallestIDTieBreak(t *testing.T) {
	jobs := []Job{
		{ID: "y", Priority: 0},
		{ID: "x", Priority: 0},
		{ID: "z", Priority: 0},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	// Equal priorities: lexicographic by ID.
	if want := []string{"x", "y", "z"}; !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestSchedulePriorityBeatsID(t *testing.T) {
	// "z" has higher priority than "a", so it must come first even though
	// "a" is the smaller ID.
	jobs := []Job{
		{ID: "a", Priority: 1},
		{ID: "z", Priority: 9},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	if want := []string{"z", "a"}; !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestScheduleIndependentJobs(t *testing.T) {
	jobs := []Job{
		{ID: "b"},
		{ID: "a"},
		{ID: "d"},
		{ID: "c"},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	// No deps, all priority 0: pure lexicographic order.
	if want := []string{"a", "b", "c", "d"}; !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestSchedulePriorityRespectsDependencies(t *testing.T) {
	// "low" has lower priority but is the only dependency-free job, so it
	// must run before the high-priority job that depends on it.
	jobs := []Job{
		{ID: "high", Deps: []string{"low"}, Priority: 100},
		{ID: "low", Priority: 1},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	if want := []string{"low", "high"}; !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestScheduleComplexDeterministic(t *testing.T) {
	jobs := []Job{
		{ID: "build", Deps: []string{"compile"}, Priority: 5},
		{ID: "compile", Deps: []string{"fetch"}, Priority: 5},
		{ID: "fetch", Priority: 5},
		{ID: "lint", Deps: []string{"fetch"}, Priority: 10},
		{ID: "test", Deps: []string{"build", "lint"}, Priority: 1},
		{ID: "docs", Deps: []string{"fetch"}, Priority: 10},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	// fetch first (only ready). Then ready={compile(5), lint(10), docs(10)}.
	// docs and lint tie at 10 -> docs < lint by ID. Then lint. Then compile.
	// After compile -> build ready. build(5). Then test.
	want := []string{"fetch", "docs", "lint", "compile", "build", "test"}
	if !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestScheduleDuplicateDepsIgnored(t *testing.T) {
	jobs := []Job{
		{ID: "b", Deps: []string{"a", "a", "a"}},
		{ID: "a"},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	if want := []string{"a", "b"}; !reflect.DeepEqual(got, want) {
		t.Fatalf("Schedule = %v, want %v", got, want)
	}
}

func TestScheduleCycleError(t *testing.T) {
	jobs := []Job{
		{ID: "a", Deps: []string{"b"}},
		{ID: "b", Deps: []string{"a"}},
	}
	got, err := Schedule(jobs)
	if err == nil {
		t.Fatalf("expected error for cycle, got order %v", got)
	}
	if len(got) != 0 {
		t.Fatalf("on cycle error, want empty slice, got %v", got)
	}
}

func TestScheduleLongerCycleError(t *testing.T) {
	jobs := []Job{
		{ID: "x"}, // schedulable
		{ID: "a", Deps: []string{"c"}},
		{ID: "b", Deps: []string{"a"}},
		{ID: "c", Deps: []string{"b"}},
	}
	got, err := Schedule(jobs)
	if err == nil {
		t.Fatalf("expected error for 3-node cycle, got order %v", got)
	}
	if len(got) != 0 {
		t.Fatalf("on cycle error, want empty slice, got %v", got)
	}
}

func TestScheduleSelfDependencyError(t *testing.T) {
	jobs := []Job{
		{ID: "a", Deps: []string{"a"}},
	}
	got, err := Schedule(jobs)
	if err == nil {
		t.Fatalf("expected error for self-dependency, got order %v", got)
	}
	if len(got) != 0 {
		t.Fatalf("on self-dependency error, want empty slice, got %v", got)
	}
}

func TestScheduleUnknownDepError(t *testing.T) {
	jobs := []Job{
		{ID: "a", Deps: []string{"ghost"}},
	}
	got, err := Schedule(jobs)
	if err == nil {
		t.Fatalf("expected error for unknown dep, got order %v", got)
	}
	if len(got) != 0 {
		t.Fatalf("on unknown-dep error, want empty slice, got %v", got)
	}
}

func TestScheduleDuplicateIDError(t *testing.T) {
	jobs := []Job{
		{ID: "a"},
		{ID: "a"},
	}
	got, err := Schedule(jobs)
	if err == nil {
		t.Fatalf("expected error for duplicate ID, got order %v", got)
	}
	if len(got) != 0 {
		t.Fatalf("on duplicate-ID error, want empty slice, got %v", got)
	}
}

func TestScheduleOutputIsValidTopoOrder(t *testing.T) {
	jobs := []Job{
		{ID: "a"},
		{ID: "b", Deps: []string{"a"}},
		{ID: "c", Deps: []string{"a"}},
		{ID: "d", Deps: []string{"b", "c"}},
		{ID: "e", Deps: []string{"d"}},
	}
	got, err := Schedule(jobs)
	if err != nil {
		t.Fatalf("unexpected error: %v", err)
	}
	if len(got) != len(jobs) {
		t.Fatalf("got %d ids, want %d", len(got), len(jobs))
	}
	pos := make(map[string]int, len(got))
	for i, id := range got {
		if _, dup := pos[id]; dup {
			t.Fatalf("id %q appears more than once in %v", id, got)
		}
		pos[id] = i
	}
	for _, j := range jobs {
		for _, dep := range j.Deps {
			if pos[dep] >= pos[j.ID] {
				t.Fatalf("dependency %q (pos %d) not before %q (pos %d) in %v",
					dep, pos[dep], j.ID, pos[j.ID], got)
			}
		}
	}
}

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.

```go
package challenge

import (
	"errors"
	"fmt"
	"sort"
)

type Job struct {
	ID       string
	Deps     []string
	Priority int
}

func Schedule(jobs []Job) ([]string, error) {
	if len(jobs) == 0 {
		return []string{}, nil
	}

	jobIDs := make(map[string]bool)
	dependencyCount := make(map[string]int)
	dependencyGraph := make(map[string][]string)
	for _, job := range jobs {
		if _, exists := jobIDs[job.ID]; exists {
			return nil, errors.New("duplicate ID")
		}
		jobIDs[job.ID] = true
		dependencyCount[job.ID] = 0
		dependencyGraph[job.ID] = make([]string, 0)
		for _, dep := range job.Deps {
			if _, exists := jobIDs[dep]; !exists {
				return nil, errors.New("unknown dependency")
			}
			dependencyCount[dep]++
			dependencyGraph[dep] = append(dependencyGraph[dep], job.ID)
		}
		dependencyCount[job.ID]++
	}

	var readyJobs []string
	for id, count := range dependencyCount {
		if count == 0 {
			readyJobs = append(readyJobs, id)
		}
	}

	var output []string
	for len(readyJobs) > 0 {
		sort.Slice(readyJobs, func(i, j int) bool {
			p1, p2 := jobs[readyJobs[i]].Priority, jobs[readyJobs[j]].Priority
			if p1 != p2 {
				return p1 > p2
			}
			return jobs[readyJobs[i]].ID < jobs[readyJobs[j]].ID
		})

		current := readyJobs[0]
		output = append(output, current)
		readyJobs = readyJobs[1:]
		for _, dep := range dependencyGraph[current] {
			dependencyCount[dep]--
			if dependencyCount[dep] == 0 {
				readyJobs = append(readyJobs, dep)
			}
		}
	}

	for _, count := range dependencyCount {
		if count > 0 {
			return nil, errors.New("cycle detected")
		}
	}

	return output, nil
}
```

[
  {
    "total": 1,
    "answer": "```go\npackage challenge\n\nimport (\n\t\"errors\"\n\t\"fmt\"\n\t\"sort\"\n)\n\ntype Job struct {\n\tID       string\n\tDeps     []string\n\tPriority int\n}\n\nfunc Schedule(jobs []Job) ([]string, error) {\n\tif len(jobs) == 0 {\n\t\treturn []string{}, nil\n\t}\n\n\tjobIDs := make(map[string]bool)\n\tdependencyCount := make(map[string]int)\n\tdependencyGraph := make(map[string][]string)\n\tfor _, job := range jobs {\n\t\tif _, exists := jobIDs[job.ID]; exists {\n\t\t\treturn nil, errors.New(\"duplicate ID\")\n\t\t}\n\t\tjobIDs[job.ID] = true\n\t\tdependencyCount[job.ID] = 0\n\t\tdependencyGraph[job.ID] = make([]string, 0)\n\t\tfor _, dep := range job.Deps {\n\t\t\tif _, exists := jobIDs[dep]; !exists {\n\t\t\t\treturn nil, errors.New(\"unknown dependency\")\n\t\t\t}\n\t\t\tdependencyCount[dep]++\n\t\t\tdependencyGraph[dep] = append(dependencyGraph[dep], job.ID)\n\t\t}\n\t\tdependencyCount[job.ID]++\n\t}\n\n\tvar readyJobs []string\n\tfor id, count := range dependencyCount {\n\t\tif count == 0 {\n\t\t\treadyJobs = append(readyJobs, id)\n\t\t}\n\t}\n\n\tvar output []string\n\tfor len(readyJobs) > 0 {\n\t\tsort.Slice(readyJobs, func(i, j int) bool {\n\t\t\tp1, p2 := jobs[readyJobs[i]].Priority, jobs[readyJobs[j]].Priority\n\t\t\tif p1 != p2 {\n\t\t\t\treturn p1 > p2\n\t\t\t}\n\t\t\treturn jobs[readyJobs[i]].ID < jobs[readyJobs[j]].ID\n\t\t})\n\n\t\tcurrent := readyJobs[0]\n\t\toutput = append(output, current)\n\t\treadyJobs = readyJobs[1:]\n\t\tfor _, dep := range dependencyGraph[current] {\n\t\t\tdependencyCount[dep]--\n\t\t\tif dependencyCount[dep] == 0 {\n\t\t\t\treadyJobs = append(readyJobs, dep)\n\t\t\t}\n\t\t}\n\t}\n\n\tfor _, count := range dependencyCount {\n\t\tif count > 0 {\n\t\t\treturn nil, errors.New(\"cycle detected\")\n\t\t}\n\t}\n\n\treturn output, nil\n}\n```",
    "passed": 0,
    "test_error": "{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"# challenge [challenge.test]\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:5:2: \\\"fmt\\\" imported and not used\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:50:19: invalid argument: index readyJobs[i] (variable of type string) must be integer\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:50:48: invalid argument: index readyJobs[j] (variable of type string) must be integer\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:54:16: invalid argument: index readyJobs[i] (variable of type string) must be integer\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:54:40: invalid argument: index readyJobs[j] (variable of type string) must be integer\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-fail\"}\n{\"Time\":\"2026-07-03T03:10:15.879019727+02:00\",\"Action\":\"start\",\"Package\":\"challenge\"}\n{\"Time\":\"2026-07-03T03:10:15.879081747+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge [build failed]\\n\"}\n{\"Time\":\"2026-07-03T03:10:15.879086827+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":0,\"FailedBuild\":\"challenge [challenge.test]\"}"
  },
  {
    "total": 1,
    "answer": "```go\npackage challenge\n\nimport (\n\t\"errors\"\n\t\"fmt\"\n\t\"sort\"\n)\n\ntype Job struct {\n\tID       string\n\tDeps     []string\n\tPriority int\n}\n\nfunc Schedule(jobs []Job) ([]string, error) {\n\tif len(jobs) == 0 {\n\t\treturn []string{}, nil\n\t}\n\n\tjobIDs := make(map[string]bool)\n\tdependencyCount := make(map[string]int)\n\tdependencyGraph := make(map[string][]string)\n\tfor _, job := range jobs {\n\t\tif _, exists := jobIDs[job.ID]; exists {\n\t\t\treturn nil, errors.New(\"duplicate ID\")\n\t\t}\n\t\tjobIDs[job.ID] = true\n\t\tdependencyCount[job.ID] = 0\n\t\tdependencyGraph[job.ID] = make([]string, 0)\n\t\tfor _, dep := range job.Deps {\n\t\t\tif _, exists := jobIDs[dep]; !exists {\n\t\t\t\treturn nil, errors.New(\"unknown dependency\")\n\t\t\t}\n\t\t\tdependencyCount[dep]++\n\t\t\tdependencyGraph[dep] = append(dependencyGraph[dep], job.ID)\n\t\t}\n\t\tdependencyCount[job.ID]++\n\t}\n\n\tvar readyJobs []string\n\tfor id, count := range dependencyCount {\n\t\tif count == 0 {\n\t\t\treadyJobs = append(readyJobs, id)\n\t\t}\n\t}\n\n\tvar output []string\n\tfor len(readyJobs) > 0 {\n\t\tsort.Slice(readyJobs, func(i, j int) bool {\n\t\t\tp1, p2 := jobs[readyJobs[i]].Priority, jobs[readyJobs[j]].Priority\n\t\t\tif p1 != p2 {\n\t\t\t\treturn p1 > p2\n\t\t\t}\n\t\t\treturn jobs[readyJobs[i]].ID < jobs[readyJobs[j]].ID\n\t\t})\n\n\t\tcurrent := readyJobs[0]\n\t\toutput = append(output, current)\n\t\treadyJobs = readyJobs[1:]\n\t\tfor _, dep := range dependencyGraph[current] {\n\t\t\tdependencyCount[dep]--\n\t\t\tif dependencyCount[dep] == 0 {\n\t\t\t\treadyJobs = append(readyJobs, dep)\n\t\t\t}\n\t\t}\n\t}\n\n\tfor _, count := range dependencyCount {\n\t\tif count > 0 {\n\t\t\treturn nil, errors.New(\"cycle detected\")\n\t\t}\n\t}\n\n\treturn output, nil\n}\n```",
    "passed": 0,
    "test_error": "{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"# challenge [challenge.test]\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:5:2: \\\"fmt\\\" imported and not used\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:50:19: invalid argument: index readyJobs[i] (variable of type string) must be integer\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:50:48: invalid argument: index readyJobs[j] (variable of type string) must be integer\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:54:16: invalid argument: index readyJobs[i] (variable of type string) must be integer\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-output\",\"Output\":\"./solution.go:54:40: invalid argument: index readyJobs[j] (variable of type string) must be integer\\n\"}\n{\"ImportPath\":\"challenge [challenge.test]\",\"Action\":\"build-fail\"}\n{\"Time\":\"2026-07-03T03:10:20.107987229+02:00\",\"Action\":\"start\",\"Package\":\"challenge\"}\n{\"Time\":\"2026-07-03T03:10:20.108048019+02:00\",\"Action\":\"output\",\"Package\":\"challenge\",\"Output\":\"FAIL\\tchallenge [build failed]\\n\"}\n{\"Time\":\"2026-07-03T03:10:20.108053319+02:00\",\"Action\":\"fail\",\"Package\":\"challenge\",\"Elapsed\":0,\"FailedBuild\":\"challenge [challenge.test]\"}"
  },
  {
    "total": 1,
    "answer": "```go\npackage challenge\n\nimport (\n\t\"errors\"\n\t\"fmt\"\n\t\"sort\"\n)\n\ntype Job struct {\n\tID       string\n\tDeps     []string\n\tPriority int\n}\n\nfunc Schedule(jobs []Job) ([]string, error) {\n\tif len(jobs) == 0 {\n\t\treturn []string{}, nil\n\t}\n\n\tjobIDs := make(map[string]bool)\n\tdependencyCount := make(map[string]int)\n\tdependencyGraph := make(map[string][]string)\n\tfor _, job := range jobs {\n\t\tif _, exists := jobIDs[job.ID]; exists {\n\t\t\treturn nil, errors.New(\"duplicate ID\")\n\t\t}\n\t\tjobIDs[job.ID] = true\n\t\tdependencyCount[job.ID] = 0\n\t\tdependencyGraph[job.ID] = make([]string, 0)\n\t\tfor _, dep := range job.Deps {\n\t\t\tif _, exists := jobIDs[dep]; !exists {\n\t\t\t\treturn nil, errors.New(\"unknown dependency\")\n\t\t\t}\n\t\t\tdependencyCount[dep]++\n\t\t\tdependencyGraph[dep] = append(dependencyGraph[dep], job.ID)\n\t\t}\n\t\tdependencyCount[job.ID]++\n\t}\n\n\tvar readyJobs []string\n\tfor id, count := range dependencyCount {\n\t\tif count == 0 {\n\t\t\treadyJobs = append(readyJobs, id)\n\t\t}\n\t}\n\n\tvar output []string\n\tfor len(readyJobs) > 0 {\n\t\tsort.Slice(readyJobs, func(i, j int) bool {\n\t\t\tp1, p2 := jobs[readyJobs[i]].Priority, jobs[readyJobs[j]].Priority\n\t\t\tif p1 != p2 {\n\t\t\t\treturn p1 > p2\n\t\t\t}\n\t\t\treturn jobs[readyJobs[i]].ID < jobs[readyJobs[j]].ID\n\t\t})\n\n\t\tcurrent := readyJobs[0]\n\t\toutput = append(output, current)\n\t\treadyJobs = readyJobs[1:]\n\t\tfor _, dep := range dependencyGraph[current] {\n\t\t\tdependencyCount[dep]--\n\t\t\tif dependencyCount[dep] == 0 {\n\t\t\t\treadyJobs = append(readyJobs, dep)\n\t\t\t}\n\t\t}\n\t}\n\n\tfor _, count := range dependencyCount {\n\t\tif count > 0 {\n\t\t\treturn nil, errors.New(\"cycle detected\")\n\t\t}\n\t}\n\n\treturn output, nil\n}\n```",
    "passed": 0,
    "test_error": ""
  }
]