Job Scheduling with Deadlines in DSA Go

Mental Model

We want to schedule jobs to finish before their deadlines and get the most profit by picking the best jobs first.

Analogy: Imagine you have a list of tasks to do before certain times, and each task gives you some money. You want to pick tasks so you earn the most money without missing deadlines.

Jobs: [Job1: profit=20, deadline=2]
      [Job2: profit=15, deadline=2]
      [Job3: profit=10, deadline=1]
      [Job4: profit=5, deadline=3]
      [Job5: profit=1, deadline=3]

Schedule slots: 1 -> null
               2 -> null
               3 -> null

Dry Run Walkthrough

Input: Jobs: (profit, deadline) = [(20,2), (15,2), (10,1), (5,3), (1,3)]

Goal: Schedule jobs to maximize total profit without missing deadlines

Step 1: Sort jobs by profit descending

Jobs sorted: (20,2) -> (15,2) -> (10,1) -> (5,3) -> (1,3)

Why: We want to try scheduling the most profitable jobs first

Step 2: Schedule job (20,2) at latest free slot before deadline 2

Slot 1 -> null
Slot 2 -> [20] -> null
Slot 3 -> null

Why: Slot 2 is free and before deadline 2, so assign job here

Step 3: Schedule job (15,2) at latest free slot before deadline 2

Slot 1 -> [15] -> null
Slot 2 -> [20] -> null
Slot 3 -> null

Why: Slot 2 is taken, so assign job to slot 1 which is free and before deadline 2

Step 4: Schedule job (10,1) at latest free slot before deadline 1

Slot 1 -> [15] -> null
Slot 2 -> [20] -> null
Slot 3 -> null

Why: Slot 1 is taken, no free slot before deadline 1, so skip this job

Step 5: Schedule job (5,3) at latest free slot before deadline 3

Slot 1 -> [15] -> null
Slot 2 -> [20] -> null
Slot 3 -> [5] -> null

Why: Slot 3 is free and before deadline 3, assign job here

Step 6: Schedule job (1,3) at latest free slot before deadline 3

Slot 1 -> [15] -> null
Slot 2 -> [20] -> null
Slot 3 -> [5] -> null

Why: All slots before deadline 3 are taken, skip this job

Result:

Final schedule:
Slot 1 -> 15 -> null
Slot 2 -> 20 -> null
Slot 3 -> 5 -> null
Total profit = 15 + 20 + 5 = 40

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

type Job struct {
	profit   int
	deadline int
}

func jobScheduling(jobs []Job) ([]int, int) {
	// Sort jobs by profit descending
	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i].profit > jobs[j].profit
	})

	maxDeadline := 0
	for _, job := range jobs {
		if job.deadline > maxDeadline {
			maxDeadline = job.deadline
		}
	}

	slots := make([]int, maxDeadline+1) // index 0 unused
	for i := range slots {
		slots[i] = -1 // -1 means free slot
	}

	totalProfit := 0

	for _, job := range jobs {
		// Find a free slot for this job, starting from its deadline going backward
		for d := job.deadline; d > 0; d-- {
			if slots[d] == -1 {
				slots[d] = job.profit
				totalProfit += job.profit
				break // scheduled this job
			}
		}
	}

	// Collect scheduled jobs profits in order of slots
	result := []int{}
	for i := 1; i <= maxDeadline; i++ {
		if slots[i] != -1 {
			result = append(result, slots[i])
		}
	}

	return result, totalProfit
}

func main() {
	jobs := []Job{{20, 2}, {15, 2}, {10, 1}, {5, 3}, {1, 3}}
	scheduled, profit := jobScheduling(jobs)
	fmt.Print("Scheduled jobs profits: ")
	for i, p := range scheduled {
		if i > 0 {
			fmt.Print(" -> ")
		}
		fmt.Print(p)
	}
	fmt.Println(" -> null")
	fmt.Printf("Total profit = %d\n", profit)
}

sort.Slice(jobs, func(i, j int) bool { return jobs[i].profit > jobs[j].profit })

Sort jobs by profit descending to prioritize high profit jobs

for _, job := range jobs { if job.deadline > maxDeadline { maxDeadline = job.deadline } }

Find maximum deadline to size slots array

slots := make([]int, maxDeadline+1); for i := range slots { slots[i] = -1 }

Initialize slots array with -1 meaning free

for _, job := range jobs { for d := job.deadline; d > 0; d-- { if slots[d] == -1 { slots[d] = job.profit; totalProfit += job.profit; break } } }

Try to schedule each job at latest free slot before deadline

for i := 1; i <= maxDeadline; i++ { if slots[i] != -1 { result = append(result, slots[i]) } }

Collect scheduled jobs profits in order of slots

Output

Scheduled jobs profits: 15 -> 20 -> 5 -> null

Total profit = 40

Complexity Analysis

Time: O(n log n) because we sort the jobs by profit and then try to schedule each job in O(d) where d is max deadline, but d ≤ n so overall O(n log n)

Space: O(n) for the slots array and job list storage

vs Alternative: Naive approach tries all permutations which is O(n!), this greedy approach is efficient and practical

Edge Cases

No jobs

Returns empty schedule and zero profit

DSA Go

for _, job := range jobs { ... } // loop skipped if jobs empty

All jobs have deadline 1

Only the highest profit job is scheduled

DSA Go

for d := job.deadline; d > 0; d-- { if slots[d] == -1 { ... } }

Jobs with same profit and deadline

Schedules jobs in order they appear until slots fill

DSA Go

for _, job := range jobs { ... } scheduling loop

When to Use This Pattern

When you need to schedule tasks with deadlines to maximize profit or value, use the greedy job scheduling pattern by sorting jobs by profit and assigning them to the latest free slot before their deadline.

Common Mistakes

Mistake: Scheduling jobs at earliest free slot instead of latest free slot before deadline
Fix: Always try to assign job to the latest possible free slot before its deadline to leave earlier slots for other jobs

Mistake: Not sorting jobs by profit descending before scheduling
Fix: Sort jobs by profit descending to ensure maximum profit scheduling

Summary

Schedules jobs to maximize total profit without missing deadlines.

Use when you have tasks with deadlines and profits and want the best profit schedule.

Sort jobs by profit and assign each to the latest free slot before its deadline.

Practice

1. What is the main goal of the Job Scheduling with Deadlines problem?

easy

A. Schedule jobs in the order they appear without considering deadlines

B. Minimize the number of jobs scheduled

C. Maximize the total profit by scheduling jobs before their deadlines

D. Maximize the number of jobs scheduled regardless of profit

Solution

1. Step 1: Understand the problem objective

   The problem aims to schedule jobs so that each job finishes before its deadline and the total profit is maximized.

2. Step 2: Identify the correct goal

   Maximizing total profit while respecting deadlines is the key goal, not just scheduling all jobs or ignoring deadlines.

3. Final Answer:

   Maximize the total profit by scheduling jobs before their deadlines -> Option C

4. Quick Check:

   Goal = Maximize profit before deadlines [OK]

Hint: Focus on profit maximization within deadlines [OK]

Common Mistakes:

• Ignoring deadlines and scheduling all jobs
• Trying to minimize jobs instead of maximizing profit
• Scheduling jobs in input order without sorting

2. Which Go data structure is best suited to efficiently pick the next available time slot when scheduling jobs by deadline?

easy

A. Map (hash table)

B. Disjoint Set (Union-Find)

C. Slice (dynamic array)

D. Linked List

Solution

1. Step 1: Understand the scheduling requirement

   We need to quickly find and assign the latest free slot before a job's deadline.

2. Step 2: Identify the suitable data structure

   Disjoint Set (Union-Find) efficiently tracks and merges available slots, making it ideal for this task.

3. Final Answer:

   Disjoint Set (Union-Find) -> Option B

4. Quick Check:

   Best structure for slot tracking = Disjoint Set [OK]

Hint: Use Disjoint Set to find free slots fast [OK]

Common Mistakes:

• Using slices which require linear search
• Using maps which don't track slot unions
• Using linked lists which are inefficient for this

3. What is the output of the following Go code snippet that schedules jobs with deadlines and profits?

package main
import "fmt"
type Job struct {
  id     string
  deadline int
  profit int
}
func main() {
  jobs := []Job{{"a", 2, 100}, {"b", 1, 19}, {"c", 2, 27}, {"d", 1, 25}, {"e", 3, 15}}
  // Assume jobs are sorted by profit descending
  scheduled := []string{"a", "c", "e"}
  fmt.Println(scheduled)
}

medium

A. ["a", "c", "e"]

B. ["b", "d", "e"]

C. ["a", "b", "c"]

D. ["a", "d", "e"]

Solution

1. Step 1: Analyze the job list and sorting

   Jobs are sorted by profit descending: a(100), c(27), d(25), b(19), e(15). The code assumes scheduled jobs are a, c, e.

2. Step 2: Check feasibility of scheduled jobs

   Job a (deadline 2), c (deadline 2), e (deadline 3) can be scheduled without conflict, maximizing profit.

3. Final Answer:

   ["a", "c", "e"] -> Option A

4. Quick Check:

   Scheduled jobs = ["a", "c", "e"] [OK]

Hint: Pick jobs by profit, fit before deadlines [OK]

Common Mistakes:

• Ignoring deadlines and picking all high profit jobs
• Confusing job order in output
• Assuming jobs b or d are scheduled incorrectly

4. Identify the bug in this Go code snippet for job scheduling:

func scheduleJobs(jobs []Job) []string {
  sort.Slice(jobs, func(i, j int) bool {
    return jobs[i].profit > jobs[j].profit
  })
  result := []string{}
  slots := make([]bool, len(jobs))
  for _, job := range jobs {
    for j := job.deadline; j >= 0; j-- {
      if !slots[j] {
        slots[j] = true
        result = append(result, job.id)
        break
      }
    }
  }
  return result
}

medium

A. Slots array size should be job.deadline, not len(jobs)

B. Jobs should be sorted by deadline, not profit

C. Loop index j should not go below 1

D. Loop index j should start from job.deadline - 1

Solution

1. Step 1: Check loop index range for slot assignment

   The inner loop runs from job.deadline down to 0, but slot indices start at 0, so job.deadline is out of range.

2. Step 2: Correct loop start index

   Loop should start at job.deadline - 1 to match zero-based indexing of slots array.

3. Final Answer:

   Loop index j should start from job.deadline - 1 -> Option D

4. Quick Check:

   Indexing starts at deadline-1 [OK]

Hint: Remember zero-based indexing for slots array [OK]

Common Mistakes:

• Starting loop at job.deadline causing index out of range
• Not sorting jobs by profit first
• Ignoring zero-based indexing in Go slices

5. Given jobs with deadlines and profits: {J1: deadline=4, profit=70}, {J2: deadline=1, profit=80}, {J3: deadline=1, profit=30}, {J4: deadline=2, profit=100}, {J5: deadline=3, profit=40}, what is the maximum total profit achievable by scheduling jobs before their deadlines?

hard

A. 290

B. 190

C. 230

D. 240

Solution

1. Step 1: Sort jobs by profit descending

   Order: J4(100), J2(80), J1(70), J5(40), J3(30).

2. Step 2: Schedule jobs greedily before deadlines

   J4 deadline=2 -> slot 2
   J2 deadline=1 -> slot 1
   J1 deadline=4 -> slot 4
   J5 deadline=3 -> slot 3
   J3 deadline=1 -> slot 1 taken, skip

3. Step 3: Calculate total profit

   100 + 80 + 70 + 40 = 290 (But only 4 slots available, all used)

4. Step 4: Re-check slot assignment

   Slots: 1(J2), 2(J4), 3(J5), 4(J1). Total profit = 80 + 100 + 40 + 70 = 290

5. Final Answer:

   290 -> Option A

6. Quick Check:

   Sum profits of scheduled jobs = 290 [OK]

Hint: Schedule highest profit jobs first before deadlines [OK]

Common Mistakes:

• Scheduling low profit jobs first
• Ignoring deadline constraints
• Double booking the same slot