Job Scheduling with Deadlines in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort jobs by their deadlines in ascending order.

DSA Go

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

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' will sort in descending order, which is incorrect for earliest deadline first.

Using '==' or '!=' does not define a proper order.

Sorting jobs by ascending deadline means jobs with smaller deadlines come first, so we use '<'.

2fill in blank

medium

Complete the code to find the maximum deadline among all jobs.

DSA Go

maxDeadline := 0
for _, job := range jobs {
    if job.Deadline [1] maxDeadline {
        maxDeadline = job.Deadline
    }
}

Drag options to blanks, or click blank then click option'

A<

B!=

C==

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' will find the minimum deadline, not maximum.

Using '==' or '!=' does not help find max value.

We update maxDeadline when job.Deadline is greater than current maxDeadline.

3fill in blank

hard

Fix the error in the code that schedules jobs to maximize profit without missing deadlines.

DSA Go

slots := make([]bool, maxDeadline)
result := make([]int, maxDeadline)
for i := range result {
    result[i] = -1
}
for i := 0; i < len(jobs); i++ {
    for j := jobs[i].Deadline - 1; j >= 0; j-- {
        if slots[j] == [1] {
            slots[j] = true
            result[j] = i
            break
        }
    }
}

Drag options to blanks, or click blank then click option'

Afalse

Btrue

Cnil

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for true means slot is occupied, so job can't be assigned there.

Using nil or 0 is invalid for boolean comparison.

We check if the slot is free (false) before assigning a job to it.

4fill in blank

hard

Fill both blanks to print the scheduled jobs in order of their slots.

DSA Go

for i := 0; i < maxDeadline; i++ {
    if result[i] != [1] {
        fmt.Println("Job ID:", jobs[result[i]].[2])
    }
}

Drag options to blanks, or click blank then click option'

A-1

BID

CDeadline

DProfit

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 instead of -1 will miss unassigned slots.

Printing Deadline or Profit instead of ID is not the usual output.

We skip slots with -1 (no job) and print the job's ID.

5fill in blank

hard

Fill all three blanks to calculate total profit from scheduled jobs.

DSA Go

totalProfit := 0
for i := 0; i < maxDeadline; i++ {
    if result[i] != [1] {
        totalProfit += jobs[result[i]].[2]
    }
}
fmt.Println("Total Profit:", [3])

Drag options to blanks, or click blank then click option'

A-1

BProfit

CtotalProfit

DDeadline

Attempts:

3 left

💡 Hint

Common Mistakes

Using Deadline instead of Profit for summation.

Printing Deadline or jobs instead of totalProfit.

We sum profits of scheduled jobs (not -1) and print totalProfit.

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