Job Scheduling with Deadlines in DSA Go - Build from Scratch

Job Scheduling with Deadlines

📖 Scenario: You are managing a small workshop where you have several jobs to complete. Each job has a deadline and a profit if finished on time. You want to schedule jobs to maximize your total profit without missing deadlines.

🎯 Goal: Build a program that schedules jobs with deadlines to maximize profit. You will create the job list, set the maximum deadline, select jobs to maximize profit, and finally print the scheduled jobs.

📋 What You'll Learn

Create a slice of jobs with exact fields and values

Create a variable for the maximum deadline

Implement the job scheduling logic to maximize profit

Print the scheduled jobs in order of their scheduled time slots

💡 Why This Matters

🌍 Real World

Job scheduling is used in manufacturing, computing, and project management to optimize resource use and maximize profit or efficiency.

💼 Career

Understanding job scheduling algorithms is important for roles in software development, operations management, and systems engineering.

1

Create the list of jobs

Create a slice called jobs of type Job with these exact entries: {"id": "a", "deadline": 2, "profit": 100}, {"id": "b", "deadline": 1, "profit": 19}, {"id": "c", "deadline": 2, "profit": 27}, {"id": "d", "deadline": 1, "profit": 25}, {"id": "e", "deadline": 3, "profit": 15}. Define the Job struct with fields id string, deadline int, and profit int.

DSA Go

type Job struct {
    id string
    deadline int
    profit int
}

// Create the jobs slice with the given jobs
// Your code here

Hint

Define the Job struct first, then create the jobs slice with the exact jobs listed.

2

Set the maximum deadline

Create an integer variable called maxDeadline and set it to 3.

DSA Go

package main

import "fmt"

type Job struct {
    id       string
    deadline int
    profit   int
}

func main() {
    jobs := []Job{
        {id: "a", deadline: 2, profit: 100},
        {id: "b", deadline: 1, profit: 19},
        {id: "c", deadline: 2, profit: 27},
        {id: "d", deadline: 1, profit: 25},
        {id: "e", deadline: 3, profit: 15},
    }

    // Create maxDeadline variable and set it to 3
    // Your code here
}

Hint

Just create a variable maxDeadline and assign it the value 3.

3

Schedule jobs to maximize profit

Sort the jobs slice in descending order by profit. Then create a slice called result of strings with length maxDeadline initialized with empty strings. Create a boolean slice called slot with length maxDeadline initialized with false. Use a for loop with variable i to iterate over jobs. Inside, use another for loop with variable j starting from jobs[i].deadline - 1 down to 0. If slot[j] is false, assign jobs[i].id to result[j], set slot[j] to true, and break the inner loop.

DSA Go

package main

import "fmt"

import "sort"

type Job struct {
    id       string
    deadline int
    profit   int
}

func main() {
    jobs := []Job{
        {id: "a", deadline: 2, profit: 100},
        {id: "b", deadline: 1, profit: 19},
        {id: "c", deadline: 2, profit: 27},
        {id: "d", deadline: 1, profit: 25},
        {id: "e", deadline: 3, profit: 15},
    }

    maxDeadline := 3

    // Sort jobs by profit descending
    // Create result and slot slices
    // Schedule jobs using nested loops
    // Your code here
}

Hint

Sort jobs by profit descending. Create result and slot slices. Use nested loops to assign jobs to free slots before their deadlines.

4

Print the scheduled jobs

Use a for loop with variable i from 0 to maxDeadline - 1. Inside the loop, print the string "Slot " plus i+1 plus ": " plus result[i].

DSA Go

package main

import (
    "fmt"
    "sort"
)

type Job struct {
    id       string
    deadline int
    profit   int
}

func main() {
    jobs := []Job{
        {id: "a", deadline: 2, profit: 100},
        {id: "b", deadline: 1, profit: 19},
        {id: "c", deadline: 2, profit: 27},
        {id: "d", deadline: 1, profit: 25},
        {id: "e", deadline: 3, profit: 15},
    }

    maxDeadline := 3

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

    result := make([]string, maxDeadline)
    slot := make([]bool, maxDeadline)

    for i := 0; i = 0; j-- {
            if !slot[j] {
                result[j] = jobs[i].id
                slot[j] = true
                break
            }
        }
    }

    // Print the scheduled jobs
    // Your code here
}

Hint

Loop through result and print each slot number and the job id assigned to it.

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