Activity Selection Problem in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort activities by their finish time.

DSA Javascript

activities.sort((a, b) => a.[1] - b.finish);

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

Astart

Bindex

Cduration

Dfinish

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by start time instead of finish time.

Using a property that does not exist.

We sort activities by their finish time to select the earliest finishing activity first.

2fill in blank

medium

Complete the code to select the first activity after the last selected one.

DSA Javascript

if (activities[i].start >= activities[[1]].finish) {

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

AlastSelected

B0

Ci - 1

DselectedIndex

Attempts:

3 left

💡 Hint

Common Mistakes

Using a fixed index like 0 instead of the last selected index.

Using i - 1 which may not be the last selected activity.

We compare the start time of the current activity with the finish time of the last selected activity.

3fill in blank

hard

Fix the error in updating the last selected activity index.

DSA Javascript

lastSelected = [1];

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

A0

Bi

ClastSelected

Dactivities.length

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning 0 which resets the last selected index incorrectly.

Assigning lastSelected to itself without change.

We update lastSelected to the current activity index i after selecting it.

4fill in blank

hard

Fill both blanks to complete the loop that selects activities.

DSA Javascript

for (let i = [1]; i < activities.length; i++) {
  if (activities[i].start >= activities[[2]].finish) {
    selected.push(activities[i]);
    lastSelected = i;
  }
}

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

A1

B0

ClastSelected

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop at 0 causing duplicate selection.

Comparing with wrong index.

Start loop from 1 because first activity is selected. Compare with lastSelected index.

5fill in blank

hard

Fill all three blanks to create the function that returns selected activities.

DSA Javascript

function selectActivities(activities) {
  activities.sort((a, b) => a.[1] - b.[2]);
  let selected = [activities[0]];
  let lastSelected = 0;
  for (let i = [3]; i < activities.length; i++) {
    if (activities[i].start >= activities[lastSelected].finish) {
      selected.push(activities[i]);
      lastSelected = i;
    }
  }
  return selected;
}

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

Afinish

C1

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by start time instead of finish time.

Starting loop at 0 causing duplicate selection.

Sort by finish time (both blanks), loop starts at 1 after selecting first activity.

Practice

1. What is the main goal of the Activity Selection Problem?

easy

A. Select the maximum number of activities that don't overlap in time

B. Find the activity with the longest duration

C. Sort activities by their start times

D. Calculate the total time of all activities

Solution

1. Step 1: Understand the problem goal

   The Activity Selection Problem aims to choose the largest set of activities that do not overlap in their time intervals.

2. Step 2: Clarify what is NOT the goal

   Finding the longest activity or sorting alone does not solve the problem; the focus is on maximizing non-overlapping activities.

3. Final Answer:

   Select the maximum number of activities that don't overlap in time -> Option A

4. Quick Check:

   Maximize non-overlapping activities = Select max activities [OK]

Hint: Focus on non-overlapping activities to maximize count [OK]

Common Mistakes:

• Thinking it's about longest activity duration
• Confusing sorting with selection
• Trying to maximize total time instead of count

2. Which of the following is the correct way to sort activities by their finish time in JavaScript?

easy

A. activities.sort((a, b) => a.finish - b.finish);

B. activities.sort((a, b) => a.start - b.start);

C. activities.sort((a, b) => b.finish - a.finish);

D. activities.sort((a, b) => a.duration - b.duration);

Solution

1. Step 1: Identify sorting key for Activity Selection

   We must sort activities by their finish time in ascending order to apply the greedy approach.

2. Step 2: Choose correct JavaScript sort syntax

   The correct syntax is activities.sort((a, b) => a.finish - b.finish); which sorts by finish time ascending.

3. Final Answer:

   activities.sort((a, b) => a.finish - b.finish); -> Option A

4. Quick Check:

   Sort by finish time ascending = activities.sort((a, b) => a.finish - b.finish); [OK]

Hint: Sort activities by finish time ascending for greedy selection [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Sorting finish time descending
• Sorting by duration which is irrelevant here

3. What will be the output of the following code snippet?

const activities = [
  {start: 1, finish: 4},
  {start: 3, finish: 5},
  {start: 0, finish: 6},
  {start: 5, finish: 7},
  {start: 8, finish: 9},
  {start: 5, finish: 9}
];

activities.sort((a, b) => a.finish - b.finish);

let count = 1;
let lastFinish = activities[0].finish;

for (let i = 1; i < activities.length; i++) {
  if (activities[i].start >= lastFinish) {
    count++;
    lastFinish = activities[i].finish;
  }
}
console.log(count);

medium

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Sort activities by finish time

   Sorted activities by finish time ascending: [{start:1, finish:4}, {start:3, finish:5}, {start:0, finish:6}, {start:5, finish:7}, {start:8, finish:9}, {start:5, finish:9}].

2. Step 2: Select activities greedily

   Start with first activity (finish=4). Next, select activities starting >=4: (start=5, finish=7), count=2; then (start=8, finish=9), count=3; then (start=9, finish=9) does not exist but next is (start=5, finish=9) which starts before 9, so skip. Total count is 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Greedy selection count = 4 [OK]

Hint: Sort by finish, pick next starting after last finish [OK]

Common Mistakes:

• Not sorting activities before selection
• Counting overlapping activities
• Updating lastFinish incorrectly

4. Identify the bug in the following code for Activity Selection Problem:

function selectActivities(activities) {
  activities.sort((a, b) => a.start - b.start);
  let count = 1;
  let lastFinish = activities[0].finish;
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start > lastFinish) {
      count++;
      lastFinish = activities[i].finish;
    }
  }
  return count;
}

medium

A. Initialize count to 0 instead of 1

B. Comparison should be activities[i].start >= lastFinish

C. Sorting should be by finish time, not start time

D. No bug, code is correct

Solution

1. Step 1: Check sorting criteria

   The greedy approach requires sorting activities by their finish time, but the code sorts by start time, which is incorrect.

2. Step 2: Understand impact of wrong sorting

   Sorting by start time can cause wrong selection order, leading to suboptimal count of activities.

3. Final Answer:

   Sorting should be by finish time, not start time -> Option C

4. Quick Check:

   Sort by finish time for correct greedy selection [OK]

Hint: Always sort by finish time, not start time [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Using > instead of >= in condition (less critical)
• Incorrect initialization of count

5. Given the activities with start and finish times:

const activities = [
  {start: 2, finish: 3},
  {start: 1, finish: 4},
  {start: 5, finish: 7},
  {start: 6, finish: 9},
  {start: 8, finish: 10},
  {start: 9, finish: 11}
];

What is the maximum number of non-overlapping activities that can be selected?

hard

A. 6

B. 4

C. 5

D. 3

Solution

1. Step 1: Sort activities by finish time

   Sorted activities by finish time ascending: [{start:2, finish:3}, {start:1, finish:4}, {start:5, finish:7}, {start:6, finish:9}, {start:8, finish:10}, {start:9, finish:11}].

2. Step 2: Select activities greedily

   Select (2,3), then (5,7), then (8,10), then (9,11) overlaps with (8,10) so skip; but (6,9) overlaps with (5,7) so skip. Total count is 4.

3. Step 3: Check for more selections

   Others overlap and cannot be selected without violating non-overlap. Maximum count is 4.

4. Final Answer:

   4 -> Option B

5. Quick Check:

   Max non-overlapping activities = 4 [OK]

Hint: Sort by finish time, pick next starting after last finish [OK]

Common Mistakes:

• Not sorting activities before selection
• Selecting overlapping activities
• Ignoring start time conditions