Job Scheduling with Deadlines in DSA Typescript

Mental Model

We want to schedule jobs so that we finish as many as possible before their deadlines, picking the most profitable ones first.

Analogy: Imagine you have several tasks to do before certain times, but you can only do one task at a time. You pick the most valuable tasks that fit in your schedule without overlapping.

Jobs: [Job1: profit=20, deadline=2]
      [Job2: profit=15, deadline=2]
      [Job3: profit=10, deadline=1]
      [Job4: profit=5, deadline=3]
      [Job5: profit=1, deadline=3]

Schedule slots: 1 -> 2 -> 3 -> null
Each slot can hold one job before its deadline.

Dry Run Walkthrough

Input: Jobs: [(id=1, profit=20, deadline=2), (id=2, profit=15, deadline=2), (id=3, profit=10, deadline=1), (id=4, profit=5, deadline=3), (id=5, profit=1, deadline=3)]

Goal: Schedule jobs to maximize total profit without missing deadlines.

Step 1: Sort jobs by profit descending

Jobs sorted: [1(20,2), 2(15,2), 3(10,1), 4(5,3), 5(1,3)]

Why: We want to try scheduling the most profitable jobs first to maximize profit.

Step 2: Schedule job 1 at latest free slot before deadline 2 (slot 2)

Schedule: slot1=null -> slot2=[1] -> slot3=null

Why: Job 1 deadline is 2, slot 2 is free, so assign job 1 there.

Step 3: Schedule job 2 at latest free slot before deadline 2 (slot 1)

Schedule: slot1=[2] -> slot2=[1] -> slot3=null

Why: Slot 2 is taken, try slot 1 which is free and before deadline.

Step 4: Schedule job 3 at latest free slot before deadline 1 (slot 1)

Schedule: slot1=[2] -> slot2=[1] -> slot3=null

Why: Slot 1 is taken by job 2, no free slot before deadline 1, so skip job 3.

Step 5: Schedule job 4 at latest free slot before deadline 3 (slot 3)

Schedule: slot1=[2] -> slot2=[1] -> slot3=[4]

Why: Slot 3 is free and before deadline 3, assign job 4.

Step 6: Schedule job 5 at latest free slot before deadline 3 (slots 3,2,1 all taken)

Schedule: slot1=[2] -> slot2=[1] -> slot3=[4]

Why: No free slot before deadline 3, skip job 5.

Result:

Final schedule: slot1=[2] -> slot2=[1] -> slot3=[4]
Total profit = 15 + 20 + 5 = 40

Annotated Code

DSA Typescript

class Job {
  id: number;
  profit: number;
  deadline: number;
  constructor(id: number, profit: number, deadline: number) {
    this.id = id;
    this.profit = profit;
    this.deadline = deadline;
  }
}

function jobScheduling(jobs: Job[]): {schedule: (number | null)[], totalProfit: number} {
  // Sort jobs by profit descending
  jobs.sort((a, b) => b.profit - a.profit);

  // Find max deadline to size schedule
  const maxDeadline = jobs.length === 0 ? 0 : Math.max(...jobs.map(job => job.deadline));

  // Initialize schedule slots with null (empty)
  const schedule: (number | null)[] = new Array(maxDeadline).fill(null);

  let totalProfit = 0;

  for (const job of jobs) {
    // Try to schedule job at latest free slot before deadline
    for (let slot = Math.min(job.deadline, maxDeadline) - 1; slot >= 0; slot--) {
      if (schedule[slot] === null) {
        schedule[slot] = job.id; // assign job id to slot
        totalProfit += job.profit;
        break; // job scheduled, move to next job
      }
    }
  }

  return {schedule, totalProfit};
}

// Driver code
const jobs = [
  new Job(1, 20, 2),
  new Job(2, 15, 2),
  new Job(3, 10, 1),
  new Job(4, 5, 3),
  new Job(5, 1, 3),
];

const result = jobScheduling(jobs);
console.log("Schedule slots (index+1):", result.schedule);
console.log("Total profit:", result.totalProfit);

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

Sort jobs by profit descending to prioritize high profit jobs

const maxDeadline = Math.max(...jobs.map(job => job.deadline));

Find maximum deadline to know schedule size

const schedule: (number | null)[] = new Array(maxDeadline).fill(null);

Initialize schedule slots as empty

for (const job of jobs) {

Iterate over jobs in profit order

for (let slot = Math.min(job.deadline, maxDeadline) - 1; slot >= 0; slot--) {

Try to assign job to latest free slot before deadline

if (schedule[slot] === null) {

Check if slot is free

schedule[slot] = job.id; totalProfit += job.profit; break;

Assign job to slot, add profit, stop searching slots

Output

Schedule slots (index+1): [ 2, 1, 4 ]

Total profit: 40

Complexity Analysis

Time: O(n log n) because we sort n jobs by profit and then for each job try to find a slot in O(d) where d is max deadline, which is at most n.

Space: O(n) for the schedule array and job list storage.

vs Alternative: Naive approach tries all permutations with factorial time; this greedy approach is efficient and practical.

Edge Cases

No jobs

Returns empty schedule and zero profit

DSA Typescript

const maxDeadline = jobs.length === 0 ? 0 : Math.max(...jobs.map(job => job.deadline));

All jobs have deadline 1

Only the highest profit job is scheduled in slot 1

DSA Typescript

for (let slot = Math.min(job.deadline, maxDeadline) - 1; slot >= 0; slot--)

Jobs with same profit and deadline

Schedules jobs in order they appear after sorting, filling earliest slots

DSA Typescript

if (schedule[slot] === null)

When to Use This Pattern

When you see tasks with deadlines and profits and need to maximize profit by scheduling without overlap, use the greedy job scheduling pattern by sorting jobs by profit and placing them in latest possible free slots.

Common Mistakes

Mistake: Scheduling jobs at earliest free slot instead of latest free slot before deadline.
Fix: Try slots from deadline backwards to find the latest free slot to maximize scheduling options.

Mistake: Not sorting jobs by profit descending before scheduling.
Fix: Sort jobs by profit descending to prioritize high profit jobs first.

Summary

Schedules jobs to maximize total profit without missing deadlines.

Use when you have tasks with deadlines and profits and want to maximize profit by scheduling non-overlapping tasks.

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