Job Scheduling with Deadlines in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort jobs by their profit in descending order.

DSA Javascript

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

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

Aprofit

Bdeadline

Cid

Dduration

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by deadline instead of profit.

Using ascending order instead of descending.

We sort jobs by their profit property in descending order to maximize total profit.

2fill in blank

medium

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

DSA Javascript

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

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

Aprofit

Bdeadline

Cid

Dduration

Attempts:

3 left

💡 Hint

Common Mistakes

Using profit instead of deadline.

Not using spread operator with Math.max.

We find the maximum deadline to know the total number of time slots available.

3fill in blank

hard

Fix the error in the code to assign a job to the latest available slot before its deadline.

DSA Javascript

for (let j = Math.min(maxDeadline, job.[1]) - 1; j >= 0; j--) {
  if (!slots[j]) {
    slots[j] = job;
    break;
  }
}

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

Aduration

Bprofit

Cid

Ddeadline

Attempts:

3 left

💡 Hint

Common Mistakes

Using profit instead of deadline in the loop.

Starting loop from wrong index.

We use job.deadline to find the latest slot before the deadline to schedule the job.

4fill in blank

hard

Fill both blanks to calculate total profit and count of scheduled jobs.

DSA Javascript

let totalProfit = 0;
let count = 0;
for (const job of slots) {
  if (job) {
    totalProfit += job.[1];
    count += [2];
  }
}

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

Aprofit

B1

C0

Ddeadline

Attempts:

3 left

💡 Hint

Common Mistakes

Adding deadline instead of profit.

Incrementing count by 0 or job.deadline.

We add job.profit to totalProfit and increment count by 1 for each scheduled job.

5fill in blank

hard

Fill the blanks to return the result as an object with count and totalProfit.

DSA Javascript

return {
  [1]: count,
  [2]: totalProfit,
  message: 'Jobs scheduled successfully'
};

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

Acount

BtotalProfit

Cprofit

DjobsCount

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong keys like 'profit' or 'jobsCount' instead of 'count' and 'totalProfit'.

We return an object with keys count and totalProfit, and a message.

Practice

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

easy

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

B. Minimize the number of jobs scheduled

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

D. Maximize the number of jobs scheduled regardless of profit

Solution

1. Step 1: Understand the problem goal

   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 objective

   Maximizing total profit means choosing jobs carefully, not just scheduling all or in order.

3. Final Answer:

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

4. Quick Check:

   Goal = Maximize profit before deadlines [OK]

Hint: Focus on profit and deadlines to maximize earnings [OK]

Common Mistakes:

• Ignoring deadlines and scheduling all jobs
• Trying to schedule jobs in input order
• Maximizing number of jobs instead of profit

2. Which of the following is the correct way to sort jobs by profit in descending order in JavaScript?

easy

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

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

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

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

Solution

1. Step 1: Understand sorting by profit descending

   To sort descending, subtract b.profit - a.profit so higher profits come first.

2. Step 2: Check the options

   jobs.sort((a, b) => b.profit - a.profit); uses b.profit - a.profit, which sorts descending by profit correctly.

3. Final Answer:

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

4. Quick Check:

   Descending profit sort = b.profit - a.profit [OK]

Hint: Use b - a for descending numeric sort in JavaScript [OK]

Common Mistakes:

• Using a.profit - b.profit which sorts ascending
• Sorting by deadline instead of profit
• Confusing ascending and descending order

3. Given the jobs array:

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

After scheduling jobs to maximize profit with deadlines, which jobs are selected (in order of scheduling)?

medium

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

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

C. ['a', 'd']

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

Solution

1. Step 1: Sort jobs by profit descending

   Sorted: a(100,2), c(27,2), d(25,1), b(19,1), e(15,3)

2. Step 2: Schedule jobs greedily before deadlines

   Schedule 'a' at latest slot <=2 (slot 2), 'c' at latest <=2 (slot 1 since 2 taken), skip 'b' (slot 1 taken), 'd' at slot 1 (since 'c' was assigned slot 1, 'd' cannot be assigned), 'e' at latest <=3 (slot 3). Correct scheduling is 'a' at slot 2, 'd' at slot 1, 'e' at slot 3. Order: ['a', 'd', 'e']

3. Final Answer:

   ['a', 'd', 'e'] -> Option D

4. Quick Check:

   Max profit jobs scheduled = ['a', 'd', 'e'] [OK]

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

Common Mistakes:

• Scheduling jobs only by deadline order
• Ignoring profit and picking lower profit jobs
• Not checking slot availability before deadline

4. Consider this code snippet for job scheduling:

jobs.sort((a, b) => b.profit - a.profit);
const result = [];
const slot = Array(jobs.length).fill(false);
for (let job of jobs) {
  for (let j = 0; j <= job.deadline; j++) {
    if (!slot[j]) {
      slot[j] = true;
      result.push(job.id);
      break;
    }
  }
}
console.log(result);

What is the main bug in this code?

medium

A. The jobs array is not sorted by deadline

B. The slot array should be initialized with true, not false

C. The inner loop should run from job.deadline down to 1, not 0 up to deadline

D. The result array should store job profits, not ids

Solution

1. Step 1: Analyze slot assignment loop

   The inner loop checks slots from 0 up to deadline, but slots should be checked from deadline down to 1 to assign latest free slot.

2. Step 2: Understand correct slot checking order

   Checking from deadline down ensures jobs are scheduled as late as possible before deadline, maximizing slot usage.

3. Final Answer:

   The inner loop should run from job.deadline down to 1, not 0 up to deadline -> Option C

4. Quick Check:

   Check slots backward from deadline [OK]

Hint: Check slots backward from deadline to assign latest free slot [OK]

Common Mistakes:

• Checking slots forward from 0 wastes early slots
• Initializing slot array incorrectly
• Confusing sorting criteria

5. You have jobs with deadlines and profits:

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

Using job scheduling with deadlines, what is the maximum total profit and which jobs are scheduled?

hard

A. Total profit 290; jobs scheduled: ['j4', 'j2', 'j1', 'j5']

B. Total profit 220; jobs scheduled: ['j2', 'j4', 'j1']

C. Total profit 240; jobs scheduled: ['j4', 'j2', 'j5', 'j3']

D. Total profit 210; jobs scheduled: ['j2', 'j4', 'j5']

Solution

1. Step 1: Sort jobs by profit descending

   Sorted: j4(100,2), j2(80,1), j1(70,4), j5(40,3), j3(30,1)

2. Step 2: Schedule jobs greedily before deadlines

   Assign j4 at slot 2, j2 at slot 1, j1 at slot 4, j5 at slot 3. j3 cannot fit. Total profit: 100+80+70+40=290. Scheduled: ['j4', 'j2', 'j1', 'j5']

3. Final Answer:

   Total profit 290; jobs scheduled: ['j4', 'j2', 'j1', 'j5'] -> Option A

4. Quick Check:

   Max profit = 290 with jobs j4,j2,j1,j5 [OK]

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

Common Mistakes:

• Not assigning jobs to latest possible slot
• Miscounting total profit
• Ignoring job deadlines when scheduling