Job Scheduling with Deadlines in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort jobs by their deadlines in ascending order.

DSA Typescript

jobs.sort((a, b) => a.deadline [1] b.deadline);

Drag options to blanks, or click blank then click option'

A-

B<

C+

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using comparison operators like '<' or '>' directly inside sort callback.

Returning boolean instead of number in sort function.

The sort function expects a negative number if a should come before b. Using 'a.deadline - b.deadline' sorts ascending by deadline.

2fill in blank

medium

Complete the code to find the maximum deadline among all jobs.

DSA Typescript

const maxDeadline = Math.max(...jobs.map(job => job.[1]));

Drag options to blanks, or click blank then click option'

Aid

Bprofit

Cdeadline

Dduration

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'profit' or other properties instead of 'deadline'.

Not using spread operator with Math.max.

We want the maximum deadline, so we map each job to its deadline property.

3fill in blank

hard

Fix the error in the code that schedules jobs to maximize profit without missing deadlines.

DSA Typescript

for (let i = 0; i < jobs.length; i++) {
  let j = Math.min(maxDeadline, jobs[i].deadline) - 1;
  while (j >= 0 && slot[j] [1] true) {
    j--;
  }
  if (j >= 0) {
    slot[j] = true;
    result[j] = jobs[i];
  }
}

Drag options to blanks, or click blank then click option'

A!=

B==

C===

D!==

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' or '!==' which would check for false slots incorrectly.

Using assignment '=' instead of comparison.

We check if the slot is already taken (true), so we continue while slot[j] == true.

4fill in blank

hard

Fill both blanks to complete the function that returns the scheduled jobs in order of their slots.

DSA Typescript

function getScheduledJobs(result: (Job | null)[]): Job[] {
  return result.filter(job => job [1] null).[2]((jobA, jobB) => jobA.deadline - jobB.deadline);
}

Drag options to blanks, or click blank then click option'

A!==

Bsort

C==

Dmap

Attempts:

3 left

💡 Hint

Common Mistakes

Using '==' instead of '!==' in filter.

Using 'map' instead of 'sort' after filtering.

We filter out null jobs using '!== null' and then sort the scheduled jobs by their deadline.

5fill in blank

hard

Fill all three blanks to complete the job scheduling function that returns the maximum profit and scheduled jobs.

DSA Typescript

function scheduleJobs(jobs: Job[]): { maxProfit: number; scheduledJobs: Job[] } {
  jobs.sort((a, b) => b.[1] - a.[2]);
  const maxDeadline = Math.max(...jobs.map(job => job.[3]));
  const slot: boolean[] = Array(maxDeadline).fill(false);
  const result: (Job | null)[] = Array(maxDeadline).fill(null);
  let maxProfit = 0;
  for (const job of jobs) {
    let j = Math.min(maxDeadline, job.deadline) - 1;
    while (j >= 0 && slot[j]) { j--; }
    if (j >= 0) {
      slot[j] = true;
      result[j] = job;
      maxProfit += job.profit;
    }
  }
  return { maxProfit, scheduledJobs: result.filter(job => job !== null) as Job[] };
}

Drag options to blanks, or click blank then click option'

Aprofit

Cdeadline

Did

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by deadline instead of profit.

Using wrong properties in sort or max calculation.

Sort jobs by profit descending (b.profit - a.profit), find max deadline from job.deadline.

Practice

1. What is the main goal of the Job Scheduling with Deadlines problem?

easy

A. Maximize the number of jobs without considering profit

B. Minimize the number of jobs scheduled

C. Schedule jobs in the order they appear without considering deadlines

D. Maximize the total profit by scheduling jobs before their deadlines

Solution

1. Step 1: Understand the problem goal

   The problem asks to schedule jobs so that total profit is maximized while respecting deadlines.

2. Step 2: Identify the objective

   Scheduling jobs before their deadlines to get maximum profit is the main goal.

3. Final Answer:

   Maximize the total profit by scheduling jobs before their deadlines -> Option D

4. Quick Check:

   Goal = Maximize profit with deadlines [OK]

Hint: Focus on maximizing profit 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 of the following TypeScript code snippets correctly declares a job interface with id, deadline, and profit properties?

easy

A. type Job = { id: string; deadline: string; profit: string }

B. class Job { id; deadline; profit; }

C. interface Job { id: number; deadline: number; profit: number; }

D. interface Job { id; deadline; profit; }

Solution

1. Step 1: Check correct TypeScript interface syntax

   interface Job { id: number; deadline: number; profit: number; } correctly declares an interface with typed properties.

2. Step 2: Identify incorrect options

   type Job = { id: string; deadline: string; profit: string } uses strings instead of numbers, class Job { id; deadline; profit; } is a class without types, interface Job { id; deadline; profit; } misses types.

3. Final Answer:

   interface Job { id: number; deadline: number; profit: number; } -> Option C

4. Quick Check:

   Correct interface syntax = interface Job { id: number; deadline: number; profit: number; } [OK]

Hint: Use interface with typed properties for job data [OK]

Common Mistakes:

• Using class without types for data structure
• Omitting types in interface properties
• Using wrong types like string for numeric fields

3. What will be the output of the following TypeScript code that schedules jobs to maximize profit?

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 },
  { id: 'd', deadline: 1, profit: 25 },
  { id: 'e', deadline: 3, profit: 15 }
];

function scheduleJobs(jobs: Job[]): string[] {
  jobs.sort((a, b) => b.profit - a.profit);
  const result: (string | null)[] = Array(jobs.length).fill(null);
  for (const job of jobs) {
    for (let j = Math.min(jobs.length, job.deadline) - 1; j >= 0; j--) {
      if (result[j] === null) {
        result[j] = job.id;
        break;
      }
    }
  }
  return result.filter(id => id !== null) as string[];
}

console.log(scheduleJobs(jobs));

medium

A. ['a', 'd', 'e']

B. ['a', 'c', 'e']

C. ['b', 'd', 'e']

D. ['a', 'b', 'c']

Solution

1. Step 1: Sort jobs by profit descending

   Sorted jobs: a(100), c(27), d(25), b(19), e(15).

2. Step 2: Schedule jobs in latest available slot before deadline

   Job 'a' scheduled at slot 1 (deadline 2), 'c' at slot 0 (deadline 2), 'd' cannot fit before deadline 1 (slot 0 taken), 'b' cannot fit, 'e' scheduled at slot 2 (deadline 3).

3. Final Answer:

   ['a', 'c', 'e'] -> Option B

4. Quick Check:

   Scheduled jobs = ['a', 'c', 'e'] [OK]

Hint: Sort by profit, assign latest free slot before deadline [OK]

Common Mistakes:

• Scheduling jobs in input order without sorting
• Assigning earliest slot instead of latest
• Ignoring deadline constraints

4. Identify the bug in the following TypeScript function for job scheduling and select the correct fix.

function scheduleJobs(jobs: Job[]): string[] {
  jobs.sort((a, b) => a.profit - b.profit);
  const result: (string | null)[] = Array(jobs.length).fill(null);
  for (const job of jobs) {
    for (let j = job.deadline - 1; j >= 0; j--) {
      if (result[j] === null) {
        result[j] = job.id;
        break;
      }
    }
  }
  return result.filter(id => id !== null) as string[];
}

medium

A. Sort jobs by profit descending instead of ascending

B. Initialize result array with zeros instead of null

C. Loop j from 0 to job.deadline - 1 instead of reverse

D. Remove the inner loop and assign jobs directly

Solution

1. Step 1: Analyze sorting order

   Jobs are sorted by profit ascending, which schedules low profit jobs first, reducing total profit.

2. Step 2: Correct sorting order

   Sorting by profit descending ensures high profit jobs are scheduled first for maximum profit.

3. Final Answer:

   Sort jobs by profit descending instead of ascending -> Option A

4. Quick Check:

   Profit descending sort fixes scheduling [OK]

Hint: Sort jobs by descending profit to fix scheduling [OK]

Common Mistakes:

• Sorting by ascending profit reduces total profit
• Changing loop direction incorrectly
• Using zero instead of null for empty slots

5. Given the following jobs with deadlines and profits, what is the maximum total profit achievable by scheduling jobs before their deadlines? Jobs: - Job1: deadline = 4, profit = 70 - Job2: deadline = 1, profit = 80 - Job3: deadline = 1, profit = 30 - Job4: deadline = 2, profit = 100 - Job5: deadline = 3, profit = 40 Select the correct maximum profit.

hard

A. 290

B. 210

C. 240

D. 230

Solution

1. Step 1: Sort jobs by profit descending

   Order: Job4(100), Job2(80), Job1(70), Job5(40), Job3(30).

2. Step 2: Schedule jobs in latest free slot before deadline

   Job4 at slot 1 (deadline 2), Job2 at slot 0 (deadline 1), Job1 at slot 3 (deadline 4), Job5 at slot 2 (deadline 3), Job3 cannot fit (slot 0 taken).

3. Step 3: Calculate total profit

   100 + 80 + 70 + 40 = 290, but slots are 0-based: slots 0,1,2,3 used. Actually, Job2 (deadline 1) at slot 0, Job4 (deadline 2) at slot 1, Job5 (deadline 3) at slot 2, Job1 (deadline 4) at slot 3. Total profit = 100 + 80 + 40 + 70 = 290.

4. Step 4: Re-check options

   Confirm scheduling: slots 0:Job2, 1:Job4, 2:Job5, 3:Job1. All fit, total 290.

5. Final Answer:

   290 -> Option A

6. Quick Check:

   Max profit = 290 [OK]

Hint: Schedule highest profit jobs first in latest free slot [OK]

Common Mistakes:

• Assuming all jobs fit without checking slots
• Adding profits of unscheduled jobs
• Misinterpreting deadlines as exact time slots