Job Scheduling with Deadlines in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Job Scheduling with Deadlines - Simple Case

What is the output of the following Go code that schedules jobs with deadlines to maximize profit?

DSA Go

package main

import (
	"fmt"
	"sort"
)

type Job struct {
	id     string
	deadline int
	profit int
}

func jobScheduling(jobs []Job) []string {
	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([]string, maxDeadline)
	for i := range slots {
		slots[i] = ""
	}

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

	result := []string{}
	for _, slot := range slots {
		if slot != "" {
			result = append(result, slot)
		}
	}
	return result
}

func main() {
	jobs := []Job{
		{"a", 2, 100},
		{"b", 1, 19},
		{"c", 2, 27},
		{"d", 1, 25},
		{"e", 3, 15},
	}
	result := jobScheduling(jobs)
	fmt.Println(result)
}

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

B ["a", "b", "e"]

C ["b", "d", "e"]

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

💡 Hint

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

The algorithm sorts jobs by profit descending: a(100), c(27), d(25), b(19), e(15). It assigns 'a' to slot 1 (deadline 2), 'c' to slot 0 (deadline 2), and 'e' to slot 2 (deadline 3). 'd' and 'b' cannot be scheduled because slots are taken.

🧠 Conceptual

intermediate

Maximum Number of Jobs Scheduled

Given a list of jobs with deadlines and profits, what is the maximum number of jobs that can be scheduled without missing deadlines?

A The number of jobs with the highest profits only

B The total number of jobs given

C The maximum deadline value among all jobs

D The minimum deadline value among all jobs

💡 Hint

Think about how many time slots are available to schedule jobs.

The maximum number of jobs that can be scheduled is limited by the maximum deadline because each job must be completed before or on its deadline, and only one job can be scheduled per time slot.

🔧 Debug

advanced

Identify the Bug in Job Scheduling Code

What error will the following Go code produce when scheduling jobs with deadlines?

DSA Go

package main

import (
	"fmt"
	"sort"
)

type Job struct {
	id string
	deadline int
	profit int
}

func jobScheduling(jobs []Job) []string {
	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([]string, maxDeadline)
	for i := range slots {
		slots[i] = ""
	}

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

	result := []string{}
	for _, slot := range slots {
		if slot != "" {
			result = append(result, slot)
		}
	}
	return result
}

func main() {
	jobs := []Job{
		{"a", 2, 100},
		{"b", 1, 19},
		{"c", 2, 27},
		{"d", 1, 25},
		{"e", 3, 15},
	}
	result := jobScheduling(jobs)
	fmt.Println(result)
}

A The code produces a compilation error due to invalid slice initialization

B The code runs correctly and outputs ["a", "c", "e"]

C The code causes a runtime panic due to index out of range

D The code outputs jobs in ascending order of profit, causing suboptimal scheduling

💡 Hint

Check the sorting order of jobs by profit.

The code sorts jobs by ascending profit (lowest first), which leads to scheduling low-profit jobs first and missing higher profit jobs, resulting in suboptimal output.

🚀 Application

advanced

Scheduling Jobs with Overlapping Deadlines

Given jobs with overlapping deadlines, which set of jobs maximizes total profit when scheduled?

A Jobs scheduled in the order they appear in the list

B Jobs with highest profits scheduled first within their deadlines

C Jobs with shortest duration first regardless of profit

D Jobs with earliest deadlines only

💡 Hint

Consider sorting jobs by profit and scheduling greedily.

Scheduling jobs by descending profit and placing each in the latest available slot before its deadline maximizes total profit, even with overlapping deadlines.

❓ Predict Output

expert

Output of Job Scheduling with Complex Deadlines and Profits

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

DSA Go

package main

import (
	"fmt"
	"sort"
)

type Job struct {
	id string
	deadline int
	profit int
}

func jobScheduling(jobs []Job) []string {
	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([]string, maxDeadline)
	for i := range slots {
		slots[i] = ""
	}

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

	result := []string{}
	for _, slot := range slots {
		if slot != "" {
			result = append(result, slot)
		}
	}
	return result
}

func main() {
	jobs := []Job{
		{"j1", 4, 70},
		{"j2", 1, 80},
		{"j3", 1, 30},
		{"j4", 2, 100},
		{"j5", 3, 40},
		{"j6", 2, 20},
	}
	result := jobScheduling(jobs)
	fmt.Println(result)
}

A ["j4", "j2", "j5", "j1"]

B ["j2", "j4", "j5", "j1"]

C ["j4", "j5", "j1", "j6"]

D ["j2", "j3", "j5", "j1"]

💡 Hint

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

Jobs sorted by profit: j4(100), j2(80), j1(70), j5(40), j3(30), j6(20). Scheduling: j4 at slot 1, j2 at slot 0, j1 at slot 3, j5 at slot 2. j3 and j6 cannot be scheduled.

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