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"
	"fmt"
)

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

type Item struct {
	ID       string
	Priority int
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	if pq[i].Priority != pq[j].Priority {
		return pq[i].Priority > pq[j].Priority
	}
	return pq[i].ID < pq[j].ID
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	item.index = -1
	*pq = old[:n-1]
	return item
}

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

	jobsMap := make(map[string]Job, len(jobs))
	for _, j := range jobs {
		if _, exists := jobsMap[j.ID]; exists {
			return nil, fmt.Errorf("duplicate ID: %s", j.ID)
		}
		jobsMap[j.ID] = j
	}

	for _, j := range jobs {
		for _, dep := range j.Deps {
			if _, exists := jobsMap[dep]; !exists {
				return nil, fmt.Errorf("unknown dependency: %s", dep)
			}
		}
	}

	inDegree := make(map[string]int, len(jobs))
	dependents := make(map[string][]string, len(jobs))

	for _, j := range jobs {
		inDegree[j.ID] = 0
		seen := make(map[string]bool)
		for _, dep := range j.Deps {
			if !seen[dep] {
				seen[dep] = true
				inDegree[j.ID]++
				dependents[dep] = append(dependents[dep], j.ID)
			}
		}
	}

	pq := &PriorityQueue{}
	heap.Init(pq)

	for id, deg := range inDegree {
		if deg == 0 {
			heap.Push(pq, &Item{ID: id, Priority: jobsMap[id].Priority})
		}
	}

	var result []string
	for pq.Len() > 0 {
		item := heap.Pop(pq).(*Item)
		result = append(result, item.ID)

		for _, nextID := range dependents[item.ID] {
			inDegree[nextID]--
			if inDegree[nextID] == 0 {
				heap.Push(pq, &Item{ID: nextID, Priority: jobsMap[nextID].Priority})
			}
		}
	}

	if len(result) != len(jobs) {
		return nil, fmt.Errorf("cycle detected")
	}

	return result, nil
}
```

The user wants a Go implementation of a dependency-aware job scheduler.
The function signature is:
```go
type Job struct {
    ID       string
    Deps     []string
    Priority int
}

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

Requirements:
1. Topological sort based on dependencies.
2. Deterministic selection rule:
   - Ready jobs: all dependencies scheduled.
   - Pick highest `Priority`.
   - Tie-break: lexicographically smallest `ID`.
3. Handle edge cases:
   - Empty input -> `[]string{}`, `nil`
   - Duplicate ID -> error
   - Unknown dependency -> error
   - Cycle -> error
   - Duplicate deps in a single job -> harmless
4. Use only standard library.

Let's break down the algorithm:
1. Validate input:
   - Check for duplicate IDs.
   - Check for unknown dependencies.
   - Build adjacency list / in-degree map for topological sort.
2. Use a priority queue (max-heap) to manage ready jobs.
   - The heap should order by `Priority` descending, then `ID` ascending.
3. Initialize in-degrees for all jobs.
4. Add jobs with in-degree 0 to the heap.
5. While heap is not empty:
   - Pop highest priority job.
   - Add to result.
   - For each job that depends on the popped job, decrement in-degree.
   - If in-degree becomes 0, push to heap.
6. After loop, if result length != number of jobs, there's a cycle -> return error.

Wait, the dependency direction:
Job A depends on B means B must come before A.
So edges go from B -> A.
In-degree of A is number of dependencies.
When B is scheduled, we decrement in-degree of A.

Let's refine validation:
- Map `id -> Job` to quickly look up jobs.
- Check duplicate IDs while building the map.
- Check unknown deps: for each job, for each dep, check if dep exists in map.
- Build in-degree map: `inDegree[id] = len(job.Deps)` (but wait, duplicate deps in `Deps` are allowed and harmless. So in-degree should be number of *unique* dependencies? Or just count each dep? The problem says "Duplicate entries inside a single job's Deps are allowed and harmless: the dependency just needs to be satisfied once." This implies we should treat deps as a set for in-degree calculation. So `inDegree[id]` should be the number of unique dependencies.)
- Actually, to be safe, I'll deduplicate deps when calculating in-degree, or just use a set for dependencies.

Let's use a map for jobs: `jobsMap := make(map[string]Job)`
Iterate over `jobs`:
  if _, exists := jobsMap[j.ID]; exists { return nil, fmt.Errorf("duplicate ID: %s", j.ID) }
  jobsMap[j.ID] = j

Check unknown deps:
  for _, j := range jobs {
    for _, dep := range j.Deps {
      if _, exists := jobsMap[dep]; !exists { return nil, fmt.Errorf("unknown dependency: %s", dep) }
    }
  }

Build in-degrees:
  inDegree := make(map[string]int)
  for id := range jobsMap { inDegree[id] = 0 }
  for _, j := range jobs {
    // deduplicate deps for this job
    seen := make(map[string]bool)
    uniqueDeps := 0
    for _, dep := range j.Deps {
      if !seen[dep] {
        seen[dep] = true
        uniqueDeps++
      }
    }
    inDegree[j.ID] = uniqueDeps
  }

Wait, what about self-dependency? "A self-dependency (a depends on a) is a cycle."
If a job depends on itself, `inDegree` will be at least 1, so it won't be added to the heap initially. The algorithm will detect it as a cycle because result length < total jobs. That's fine.

Priority Queue implementation:
We need a max-heap based on Priority, then min-heap based on ID.
Go's `container/heap` interface requires:
```go
type Item struct {
    ID       string
    Priority int
    index    int // needed for heap interface
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    if pq[i].Priority != pq[j].Priority {
        return pq[i].Priority > pq[j].Priority // higher priority first
    }
    return pq[i].ID < pq[j].ID // lexicographically smaller ID first
}
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil // avoid memory leak
    item.index = -1
    *pq = old[:n-1]
    return item
}
```

Wait, we also need to know which jobs depend on a given job to decrement their in-degrees.
So we need a reverse adjacency list: `dependents[id] = []string{...}`
While building in-degrees, we can also build `dependents`.
```go
dependents := make(map[string][]string)
for _, j := range jobs {
    seen := make(map[string]bool)
    for _, dep := range j.Deps {
        if !seen[dep] {
            seen[dep] = true
            dependents[dep] = append(dependents[dep], j.ID)
        }
    }
}
```

Algorithm steps:
1. Handle empty input.
2. Validate IDs and deps.
3. Build `inDegree` and `dependents`.
4. Initialize heap with jobs having `inDegree[id] == 0`.
5. Loop while heap not empty:
   - pop `item`
   - append `item.ID` to result
   - for each `nextID` in `dependents[item.ID]`:
     - `inDegree[nextID]--`
     - if `inDegree[nextID] == 0`, push to heap
6. If `len(result) != len(jobs)`, return cycle error.
7. Return result, nil.

Let's test mentally with examples.
Example 1:
c -> b, b -> a, a -> []
inDegree: a:0, b:1, c:1
dependents: a:[b], b:[c]
heap init: [a]
pop a -> res: [a], dependents[a]=[b], inDegree[b]=0 -> push b
pop b -> res: [a, b], dependents[b]=[c], inDegree[c]=0 -> push c
pop c -> res: [a, b, c]
len(res)=3 == len(jobs). OK.

Example 2:
a: P=1, b: P=5
inDegree: a:0, b:0
heap init: [a, b] -> heap orders b first (P=5 > P=1)
pop b -> res: [b]
pop a -> res: [b, a]
OK.

Example 3:
y: P=0, x: P=0
heap init: [x, y] (x < y lexicographically)
pop x -> res: [x]
pop y -> res: [x, y]
OK.

Example 4: Diamond
a: [], b: [a], c: [a], d: [b, c]
inDegree: a:0, b:1, c:1, d:2
dependents: a:[b, c], b:[d], c:[d]
heap init: [a]
pop a -> res: [a], dec b->0, c->0. push b, c.
heap has b(P=0), c(P=0). b < c, so pop b.
res: [a, b], dec d->1.
pop c -> res: [a, b, c], dec d->
…[12102 chars elided]…
atter.

All good.

Let's consider if `jobs` contains a job with `Deps` that includes itself. `seen` map will mark it, `inDegree` becomes 1. `dependents` gets entry. It won't be pushed initially. Loop finishes, `len(result) < len(jobs)`, returns cycle error. Correct.

One detail: `fmt` package is standard library. Allowed.
`container/heap` is standard library. Allowed.

The code looks complete and correct.

I will output the solution as requested.
One minor adjustment: I'll make sure the package name is `challenge` as requested.
The problem statement says: "Implement a file `solution.go` in `package challenge` exporting: ..."
So I'll wrap it in `package challenge`.

Final check of the code structure:
```go
package challenge

import (
	"container/heap"
	"fmt"
)

// ... types and functions ...
```
Matches.

I think it's ready.
One thing: `dependents` map iteration order might affect the order in which `inDegree` is decremented, but since we only push when it hits 0, and the heap orders them, the final output is deterministic. The problem statement says "This makes the result unique and fully determined by the input." So it's fine.

I will produce the final answer. 
All constraints and examples are satisfied.
Code is clean and efficient.
No extra prose.
Proceeds. 
Output matches request. 
Done. 
Let's generate. 
(Self-Correction/Verification during thought)
Wait, should `dependents` be a slice of strings or something else? Slice is fine.
Is there any chance `dependents[item.ID]` returns nil? Yes, if no job depends on it. Iterating over nil slice is safe in Go (does nothing).
`inDegree` map lookup: `inDegree[nextID]--` is safe because `nextID` is guaranteed to be in `inDegree` (validated).
`jobsMap[id].Priority` is safe.
Everything looks solid.
One minor point: `fmt.Errorf` is fine, but sometimes challenges prefer specific error types or messages. The prompt says "Return a non-nil error", so any error is fine.
I'll stick with `fmt.Errorf`.

Final code matches the drafted version.
Proceeds. 
Output generation. 
[Done]