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 (
	"container/heap"
	"errors"
	"fmt"
)

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

// jobHeap implements heap.Interface and holds Jobs.
// It orders jobs such that the "best" job (highest priority, then smallest ID)
// is at the root (index 0), which is popped first.
type jobHeap []Job

func (h jobHeap) Len() int           { return len(h) }
func (h jobHeap) Less(i, j int) bool {
	// Higher priority comes first (is "smaller" in min-heap terms)
	if h[i].Priority != h[j].Priority {
		return h[i].Priority > h[j].Priority
	}
	// Lexicographically smaller ID comes first
	return h[i].ID < h[j].ID
}
func (h jobHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *jobHeap) Push(x interface{}) {
	*h = append(*h, x.(Job))
}

func (h *jobHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[0 : n-1]
	return item
}

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

	jobMap := make(map[string]Job)
	inDegree := make(map[string]int)
	dependents := make(map[string][]string)

	// 1. Validate and store jobs
	for _, job := range jobs {
		if _, exists := jobMap[job.ID]; exists {
			return nil, fmt.Errorf("duplicate job ID: %s", job.ID)
		}
		jobMap[job.ID] = job
		inDegree[job.ID] = 0
	}

	// 2. Build dependency graph
	for _, job := range jobs {
		// Use a map to deduplicate dependencies for this job
		seenDeps := make(map[string]bool)
		for _, dep := range job.Deps {
			if seenDeps[dep] {
				continue
			}
			seenDeps[dep] = true

			if _, exists := jobMap[dep]; !exists {
				return nil, fmt.Errorf("unknown dependency: %s", dep)
			}

			// Add edge: dep -> job
			dependents[dep] = append(dependents[dep], job.ID)
			inDegree[job.ID]++
		}
	}

	// 3. Initialize priority queue with jobs having no dependencies
	h := &jobHeap{}
	heap.Init(h)
	for id, deg := range inDegree {
		if deg == 0 {
			heap.Push(h, jobMap[id])
		}
	}

	// 4. Process jobs
	var result []string
	for h.Len() > 0 {
		current := heap.Pop(h).(Job)
		result = append(result, current.ID)

		// Update neighbors
		for _, neighborID := range dependents[current.ID] {
			inDegree[neighborID]--
			if inDegree[neighborID] == 0 {
				heap.Push(h, jobMap[neighborID])
			}
		}
	}

	// 5. Check for cycles
	if len(result) != len(jobs) {
		return nil, errors.New("cycle detected in dependencies")
	}

	return result, nil
}
```

The user wants a Go implementation of a dependency-aware job scheduler.

Key requirements:
1. Package name: `challenge`
2. File name: `solution.go`
3. Type `Job` with fields `ID`, `Deps`, `Priority`.
4. Function `Schedule(jobs []Job) ([]string, error)`.
5. Topological sort based on dependencies.
6. Deterministic selection rule:
   - Ready jobs: all dependencies scheduled.
   - Pick highest `Priority`.
   - Tie-break: lexicographically smallest `ID`.
7. Error handling:
   - Empty input -> `[]string{}`, `nil`.
   - Duplicate ID -> error.
   - Unknown dependency -> error.
   - Cycle -> error.
8. Standard library only.

Algorithm:
1. Parse input jobs into a map for quick lookup and validation.
   - Check for duplicate IDs.
   - Check for unknown dependencies.
2. Compute in-degrees for each job (number of unsatisfied dependencies).
3. Use a priority queue (max-heap) to store ready jobs.
   - Heap ordering:
     - Higher Priority first.
     - If Priority equal, smaller ID first.
4. Initialize heap with jobs having in-degree 0.
5. While heap is not empty:
   - Pop job with highest priority/smallest ID.
   - Add to result.
   - For each dependent job (jobs that depend on the popped job):
     - Decrement in-degree.
     - If in-degree becomes 0, push to heap.
6. After loop, if result length != total jobs, there's a cycle -> error.
7. Return result.

Data structures:
- `jobMap`: map[string]Job to store jobs by ID.
- `inDegree`: map[string]int to track dependency counts.
- `dependents`: map[string][]string to track reverse dependencies (who depends on whom).
- `heap`: custom type implementing `container/heap` interface.

Heap implementation details:
- Store job IDs or Job structs. Storing IDs is sufficient since we have the map.
- `Less(i, j int) bool`:
  - Compare priorities: `jobs[i].Priority > jobs[j].Priority` (max-heap).
  - If equal, compare IDs: `jobs[i].ID < jobs[j].ID` (lexicographical).

Edge cases:
- Empty input.
- Self-dependency (cycle).
- Duplicate deps in a single job (handled by set logic or just counting in-degree correctly).
- Disconnected components.

Let's refine the "Duplicate entries inside a single job's Deps" rule.
If job A has Deps ["B", "B"], B is a dependency. When B is scheduled, A's in-degree should decrease by 1, not 2.
So, when building the graph, we should deduplicate dependencies for each job or handle in-degree calculation carefully.
Actually, standard Kahn's algorithm counts edges. If A depends on B twice, there are two edges A->B (or B->A in reverse graph).
If we treat them as distinct edges, in-degree of A is 2. When B is processed, we decrement A's in-degree by 2 (if we iterate over dependents list which might contain duplicates).
Wait, if A depends on B twice, does it mean B must be scheduled twice? No, "dependency just needs to be satisfied once".
So, we must deduplicate dependencies per job.
Example: Job A {Deps: ["B", "B"]}.
If we don't deduplicate:
- inDegree[A] = 2.
- dependents[B] = [A, A].
- When B is scheduled, we iterate dependents[B]. We see A, decrement inDegree[A] to 1. We see A again, decrement inDegree[A] to 0. A becomes ready.
This actually works out mathematically if we treat the graph edges exactly as listed.
However, if we use a set for dependents or deduplicate deps, it's safer and cleaner.
Let's deduplicate deps for each job to be safe and strictly follow "dependency just needs to be satisfied once".

Step-by-step implementation plan:
1. Define `Job` struct.
2. Define `Schedule` function.
3. Handle empty input.
4. Create `jobMap` and `inDegree` map.
5. Iterate jobs:
   - Check duplicate ID.
   - Store in `jobMap`.
   - Initialize `inDegree[job.ID] = 0`.
6. Iterate jobs again to build graph:
   - For each dep in `job.Deps`:
     - Check if dep exists in `jobMap`. If not, return error.
     - Add edge: `dependents[dep]` append `job.ID`.
     - Increment `inDegree[job.ID]`.
     - Note: If `job.Deps` has duplicates, `inDegree` increments multiple times.
     - To handle "Duplicate entries inside a single job's Deps are allowed and harmless", we need to ensure we don't count the same dependency twice for the same job.
     - Use a temporary map or sort/unique for deps of each job before processing.
7. Initialize heap with jobs where `inDegree[job.ID] == 0`.
8. Run loop.
9. Check for cycle.

Heap struct:
```go
type jobHeap []string

func (h jobHeap) Len() int           { return len(h) }
func (h jobHeap) Less(i, j int) bool {
    // We need access to Job data.
    // We can pass jobMap to the heap or store Job structs in heap.
    // Storing Job structs is easier for comparison.
    // But we need to update state? No, just read.
    // Let's store Job structs in heap.
}
```
Actually, storing `Job` structs in the heap is better because we need `Priority` and `ID` for comparison.
Wait, if we store `Job` structs, we need to make sure we don't modify them.
Let's define:
```go
type jobHeap []Job

func (h jobHeap) Len() int           { return len(h) }
func (h jobHeap) Less(i, j int) bool {
    if h[i].Priority != h[j].Priority {
        return h[i].Priority > h[j].Priority // Higher priority first
    }
    return h[i].ID < h[j].ID // Lexicographically smaller ID first
}
func (h jobHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *jobHeap) Push(x interface{}) {
    *h = append(*h, x.(Job))
}
func (h *jobHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[0 : n-1]
    return item
}
```

Wait, `container/heap` requires the type to implement the interface.
The `Less` function needs to access the data. If we store `Job` structs, it's self-contained.

Refining dependency handling:
Input:
```go
jobs := []Job{
    {ID: "a", Deps: []string{"b", "b"}},
    {ID: "b"},
}
```
If we just iterate `Deps`:
- `inDegree["a"]` becomes 2.
- `dependents["b"]` becomes `["a", "a"]`.
- Heap init: `b` (inDegree 0).
- Pop `b`.
- Iterate `dependents["b"]`:
  - `a`: `inDegree["a"]` becomes 1.
  - `a`: `inDegree["a"]` becomes 0. Push `a`.
- Pop `a`.
Result: `["b", "a"]`. Correct.
So strictly speaking, treating duplicates as multiple edges works fine for Kahn's algorit
…[29055 chars elided]…
h) }
func (h jobHeap) Less(i, j int) bool {
	if h[i].Priority != h[j].Priority {
		return h[i].Priority > h[j].Priority
	}
	return h[i].ID < h[j].ID
}
func (h jobHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *jobHeap) Push(x interface{}) {
	*h = append(*h, x.(Job))
}
func (h *jobHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[0 : n-1]
	return item
}

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

	jobMap := make(map[string]Job)
	inDegree := make(map[string]int)
	dependents := make(map[string][]string)

	for _, job := range jobs {
		if _, exists := jobMap[job.ID]; exists {
			return nil, fmt.Errorf("duplicate job ID: %s", job.ID)
		}
		jobMap[job.ID] = job
		inDegree[job.ID] = 0
	}

	for _, job := range jobs {
		seenDeps := make(map[string]bool)
		for _, dep := range job.Deps {
			if seenDeps[dep] {
				continue
			}
			seenDeps[dep] = true

			if _, exists := jobMap[dep]; !exists {
				return nil, fmt.Errorf("unknown dependency: %s", dep)
			}

			dependents[dep] = append(dependents[dep], job.ID)
			inDegree[job.ID]++
		}
	}

	h := &jobHeap{}
	heap.Init(h)
	for id, deg := range inDegree {
		if deg == 0 {
			heap.Push(h, jobMap[id])
		}
	}

	var result []string
	for h.Len() > 0 {
		current := heap.Pop(h).(Job)
		result = append(result, current.ID)

		for _, neighborID := range dependents[current.ID] {
			inDegree[neighborID]--
			if inDegree[neighborID] == 0 {
				heap.Push(h, jobMap[neighborID])
			}
		}
	}

	if len(result) != len(jobs) {
		return nil, errors.New("cycle detected in dependencies")
	}

	return result, nil
}
```
This is the final solution.

Wait, I should confirm the package name.
"Implement a file solution.go in package challenge".
Yes.

And the function signature.
`func Schedule(jobs []Job) ([]string, error)`
Yes.

And type Job.
Yes.

Ready.

One tiny thing:
The prompt says "Use only the Go standard library."
My imports: `container/heap`, `errors`, `fmt`.
All standard.

I will output the solution now.