Job Scheduling with Deadlines in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

The goal is to schedule jobs to maximize total profit while completing each job before its deadline.

beginner

In Job Scheduling with Deadlines, what does each job typically have?

Each job has a deadline by which it must be completed and a profit earned if completed on time.

intermediate

Why do we sort jobs by profit in descending order in the greedy approach?

Sorting by profit ensures we try to schedule the most profitable jobs first to maximize total profit.

intermediate

How do we find a free time slot for a job in the greedy scheduling algorithm?

We check from the job's deadline backward to find the latest free slot to schedule it.

advanced

What data structure can help efficiently track free time slots in Job Scheduling with Deadlines?

A disjoint set (union-find) or an array can be used to track free slots efficiently.

What is the first step in the greedy approach to Job Scheduling with Deadlines?

A Sort jobs by deadline in ascending order

B Sort jobs by profit in descending order

C Schedule jobs randomly

D Schedule jobs by shortest duration first

Sorting jobs by profit descending helps prioritize the most profitable jobs first.

If a job's deadline is 3, which time slots do we check to schedule it?

A From slot 3 backward to 1

B Only slot 3

C Any slot after 3

D From slot 1 to 3 forward

We check backward from the deadline to find the latest free slot before the deadline.

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

A The job is scheduled anyway

B The job is scheduled after the deadline

C The job is skipped

D The job's profit is doubled

If no free slot is available before the deadline, the job cannot be scheduled.

Which of these is NOT a property of jobs in Job Scheduling with Deadlines?

A Must be completed before deadline

B Profit

C Deadline

D Duration longer than 1 unit

Jobs are usually assumed to take 1 unit time; longer durations are not typical in this problem.

What is the main benefit of using a disjoint set data structure in this problem?

A Efficiently finding free time slots

B Faster sorting of jobs

C Storing job profits

D Tracking job deadlines

Disjoint sets help quickly find and union free time slots for scheduling.

Explain the greedy algorithm approach to solve Job Scheduling with Deadlines.

Think about how to pick jobs and where to place them in time.

Describe how to find a free time slot for a job with a given deadline in the scheduling process.

Imagine filling a calendar from the deadline backward.

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