Job Scheduling with Deadlines in DSA Typescript - Build from Scratch

Job Scheduling with Deadlines

📖 Scenario: You are managing a small workshop where several jobs need to be completed. Each job has a deadline and a profit if finished before or on that deadline. You want to schedule jobs to maximize your total profit.

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

📋 What You'll Learn

Create an array of jobs with exact id, deadline, and profit

Create a variable for the maximum deadline

Implement the job scheduling logic to select jobs maximizing profit

Print the scheduled jobs in order of their scheduled time slots

💡 Why This Matters

🌍 Real World

Job scheduling is used in factories, computer task management, and project planning to maximize efficiency and profit.

💼 Career

Understanding job scheduling helps in roles like software development, operations management, and systems engineering where task prioritization is key.

1

Create the job list

Create an array called jobs with these exact objects: {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}

DSA Typescript

// Create the jobs array with given job objects
// Your code here

Hint

Use const jobs = [ ... ] with the exact job objects inside.

2

Set the maximum deadline

Create a variable called maxDeadline and set it to 3, which is the maximum deadline among the jobs.

DSA Typescript

const jobs = [
  {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

Use const maxDeadline = 3; to set the maximum deadline.

3

Schedule jobs to maximize profit

Sort the jobs array by profit in descending order. Create an array called result of length maxDeadline filled with null. For each job in sorted order, find a free slot from its deadline backwards and assign the job's id to that slot in result if free.

DSA Typescript

const jobs = [
  {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}
];

const maxDeadline = 3;

// Sort jobs by profit descending and schedule them
// Your code here

Hint

Sort jobs by profit descending. Use a loop to assign each job to the latest free slot before its deadline.

4

Print the scheduled jobs

Print the result array showing scheduled job ids separated by -> . For empty slots, print null.

DSA Typescript

const jobs = [
  {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}
];

const maxDeadline = 3;

jobs.sort((a, b) => b.profit - a.profit);

const result: (string | null)[] = new Array(maxDeadline).fill(null);

for (const job of jobs) {
  for (let slot = Math.min(job.deadline, maxDeadline) - 1; slot >= 0; slot--) {
    if (result[slot] === null) {
      result[slot] = job.id;
      break;
    }
  }
}

// Print the scheduled jobs separated by ' -> '
// Your code here

Hint

Use console.log(result.map(x => x === null ? 'null' : x).join(' -> ')) to print the scheduled jobs.