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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Job Scheduling with Deadlines and Profits

What is the output of the following TypeScript code that schedules jobs to maximize profit given deadlines?

DSA Typescript

interface Job {
  id: string;
  deadline: number;
  profit: number;
}

function jobScheduling(jobs: Job[]): string {
  jobs.sort((a, b) => b.profit - a.profit);
  const n = jobs.length;
  const result: (string | null)[] = Array(n).fill(null);
  const slot: boolean[] = Array(n).fill(false);

  for (let i = 0; i < n; i++) {
    for (let j = Math.min(n - 1, jobs[i].deadline - 1); j >= 0; j--) {
      if (!slot[j]) {
        slot[j] = true;
        result[j] = jobs[i].id;
        break;
      }
    }
  }

  return result.filter(x => x !== null).join(' -> ') + ' -> null';
}

const 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 }
];

console.log(jobScheduling(jobs));

A "a -> c -> e -> null"

B "a -> d -> e -> null"

C "b -> d -> e -> null"

D "a -> b -> c -> null"

💡 Hint

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

The jobs are sorted by profit: a(100), c(27), d(25), b(19), e(15).

Assign 'a' to slot 1 (deadline 2), 'c' to slot 0 (deadline 2), and 'e' to slot 2 (deadline 3). Slots 0,1,2 correspond to time slots 1,2,3 respectively.

Resulting schedule is "a -> c -> e -> null".

🧠 Conceptual

intermediate

Maximum Number of Jobs Scheduled

Given 5 jobs with deadlines [2, 1, 2, 1, 3] and profits [100, 19, 27, 25, 15], what is the maximum number of jobs that can be scheduled without missing deadlines?

A 2

B 4

C 3

D 5

💡 Hint

Each job takes 1 unit of time. Schedule jobs greedily by profit and assign to latest free slot before deadline.

Maximum slots available are 3 (max deadline).

By scheduling jobs with highest profit first, we can schedule 3 jobs without conflicts.

🔧 Debug

advanced

Identify the Logical Error in Job Scheduling Code

What is the logical error in the following TypeScript code snippet for job scheduling with deadlines? function jobScheduling(jobs: Job[]): string { jobs.sort((a, b) => a.profit - b.profit); const n = jobs.length; const result: (string | null)[] = Array(n).fill(null); const slot: boolean[] = Array(n).fill(false); for (let i = 0; i < n; i++) { for (let j = Math.min(n - 1, jobs[i].deadline - 1); j >= 0; j--) { if (!slot[j]) { slot[j] = true; result[j] = jobs[i].id; break; } } } return result.filter(x => x !== null).join(' -> ') + ' -> null'; }

A Slots array is not initialized correctly, causing index out of range errors.

B The result array should store profits instead of job ids for correct output.

C The inner loop should iterate forwards, not backwards, to assign jobs correctly.

D Jobs are sorted in ascending order of profit instead of descending, causing suboptimal scheduling.

💡 Hint

Check the sorting order of jobs by profit.

The code sorts jobs by ascending profit, which schedules low profit jobs first.

This leads to suboptimal total profit and incorrect scheduling.

Sorting should be descending by profit.

📝 Syntax

advanced

Identify Syntax Error in Job Scheduling Code

Which option contains a syntax error in the TypeScript code for job scheduling?

DSA Typescript

interface Job {
  id: string;
  deadline: number;
  profit: number;
}

const jobs: Job[] = [
  { id: 'a', deadline: 2, profit: 100 },
  { id: 'b', deadline: 1, profit: 19 },
  { id: 'c', deadline: 2, profit: 27 }
];

function scheduleJobs(jobs: Job[]): string {
  jobs.sort((a, b) => b.profit - a.profit);
  const n = jobs.length;
  const result: (string | null)[] = Array(n).fill(null);
  const slot: boolean[] = Array(n).fill(false);

  for (let i = 0; i < n; i++) {
    for (let j = Math.min(n - 1, jobs[i].deadline - 1); j >= 0; j--) {
      if (!slot[j]) {
        slot[j] = true;
        result[j] = jobs[i].id;
        break;
      }
    }
  }

  return result.filter(x => x !== null).join(' -> ') + ' -> null';
}

A Missing semicolon after slot[j] = true inside the inner loop.

B Incorrect type annotation for result array; should be string[] not (string | null)[]

C Using Math.min with n - 1 and jobs[i].deadline - 1 causes runtime error.

D The function scheduleJobs is missing a return type annotation.

💡 Hint

Look carefully at statement endings inside loops.

TypeScript allows optional semicolons but missing semicolon after slot[j] = true can cause issues in some cases.

Other options are valid TypeScript syntax.

🚀 Application

expert

Optimal Job Scheduling Output for Complex Input

Given the following jobs with deadlines and profits, what is the optimal job schedule output string? Jobs: - {id: 'j1', deadline: 4, profit: 70} - {id: 'j2', deadline: 1, profit: 80} - {id: 'j3', deadline: 1, profit: 30} - {id: 'j4', deadline: 2, profit: 100} - {id: 'j5', deadline: 3, profit: 40} - {id: 'j6', deadline: 2, profit: 20} Use the greedy algorithm to schedule jobs to maximize profit. Each job takes 1 unit time. Output format: job ids separated by ' -> ' ending with ' -> null'.

A "j2 -> j4 -> j5 -> j1 -> null"

B "j4 -> j2 -> j5 -> j1 -> null"

C "j4 -> j5 -> j1 -> j2 -> null"

D "j2 -> j4 -> j1 -> j5 -> null"

💡 Hint

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

Sorted by profit: j4(100), j2(80), j1(70), j5(40), j3(30), j6(20).

Assign j4 to slot 1 (deadline 2), j2 to slot 0 (deadline 1), j5 to slot 2 (deadline 3), j1 to slot 3 (deadline 4).

Slots 0 to 3 correspond to time 1 to 4.

Schedule is "j4 -> j2 -> j5 -> j1 -> null".