Job Scheduling with Deadlines in DSA Go - Execution Trace

Concept Flow - Job Scheduling with Deadlines

Start with list of jobs

↓

Sort jobs by profit descending

↓

Initialize schedule slots as empty

↓

For each job in sorted list

↓

Find latest free slot before deadline

↓

If slot found, assign job to slot

↓

Repeat for all jobs

↓

Output scheduled jobs and total profit

Sort jobs by profit, then assign each to the latest free slot before its deadline to maximize total profit.

Execution Sample

DSA Go

jobs := []Job{{id:'A', deadline:2, profit:100}, {id:'B', deadline:1, profit:19}, {id:'C', deadline:2, profit:27}}
// Sort jobs by profit descending
// For each job:
//   Find slot before deadline
//   If free, assign job
// Print scheduled jobs

Schedules jobs to maximize profit by placing each job in the latest available slot before its deadline.

Execution Table

Step	Job Considered	Sorted Jobs	Slot Checked	Slot Status	Action	Scheduled Slots	Total Profit
1	Initial	[A(100,2), C(27,2), B(19,1)]	-	-	Start scheduling	[-, -]	0
2	A	[A(100,2), C(27,2), B(19,1)]	Slot 2	Free	Assign A to slot 2	[-, A]	100
3	C	[A(100,2), C(27,2), B(19,1)]	Slot 2	Occupied	Check slot 1	[-, A]	100
4	C	[A(100,2), C(27,2), B(19,1)]	Slot 1	Free	Assign C to slot 1	[C, A]	127
5	B	[A(100,2), C(27,2), B(19,1)]	Slot 1	Occupied	No slot available, skip B	[C, A]	127
6	End	-	-	-	Scheduling complete	[C, A]	127

💡 All jobs considered; no free slots left for job B before its deadline.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
Scheduled Slots	[-, -]	[-, A]	[-, A]	[C, A]	[C, A]	[C, A]
Total Profit	0	100	100	127	127	127

Key Moments - 3 Insights

Why do we sort jobs by profit before scheduling?

Sorting by profit ensures we try to schedule the most profitable jobs first, maximizing total profit as shown in execution_table rows 1 and 2.

Why do we check the latest slot before the deadline instead of the earliest?

Checking the latest slot before deadline allows earlier slots to remain free for other jobs, increasing chances to schedule more jobs, as seen in rows 3 and 4.

What happens if no free slot is found before a job's deadline?

The job is skipped and not scheduled, so it does not add to profit, as shown in row 5 for job B.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which slot was assigned to job C?

A Slot 2

B Slot 1

C No slot assigned

D Slot 3

💡 Hint

Check the 'Slot Checked' and 'Action' columns at step 4 in execution_table.

At which step does the total profit become 127?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Total Profit' column in execution_table for each step.

If job B had a deadline of 2 instead of 1, what would happen at step 5?

A Job B would still be skipped

B Job B would be assigned to slot 2

C Job B would be assigned to slot 1

D Job B would be assigned to a new slot 3

💡 Hint

Refer to how slots are checked and assigned in execution_table steps 3-5.

Concept Snapshot

Job Scheduling with Deadlines:
- Sort jobs by descending profit
- For each job, assign to latest free slot before deadline
- Skip if no slot available
- Maximizes total profit
- Schedule represented as array of slots

Full Transcript

Job Scheduling with Deadlines means we have jobs each with a deadline and profit. We want to schedule jobs to maximize profit without missing deadlines. We start by sorting jobs from highest to lowest profit. Then, for each job, we try to put it in the latest free time slot before its deadline. If that slot is taken, we check earlier slots. If no slot is free, we skip the job. This way, we fill slots with the most profitable jobs first, ensuring maximum total profit. The execution table shows each step: sorting, checking slots, assigning jobs, and updating total profit. Variables track scheduled slots and profit after each step. Key points are sorting by profit, checking latest slots first, and skipping jobs if no slot is free. The visual quiz tests understanding of slot assignment and profit updates. This method efficiently schedules jobs to get the best profit possible.

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