Activity Selection Problem in DSA Javascript - Execution Trace

Concept Flow - Activity Selection Problem

Sort activities by finish time

↓

Select first activity

↓

For each next activity

↓

Check if start >= last selected finish

↓

Select activity

↓

Repeat until all activities checked

↓

Done

Sort activities by finish time, then pick the earliest finishing activity that doesn't overlap with previously selected ones.

Execution Sample

DSA Javascript

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}
];
// Select max activities without overlap

This code selects the maximum number of activities that don't overlap based on their start and finish times.

Execution Table

Step	Operation	Current Activity	Last Selected Finish	Selected Activities	Action
1	Sort activities by finish time	-	-	[]	Activities sorted by finish time: [{1,4}, {3,5}, {0,6}, {5,7}, {8,9}, {5,9}]
2	Select first activity	{start:1, finish:4}	-	[{1,4}]	Select first activity by default
3	Check next activity	{start:3, finish:5}	4	[{1,4}]	3 < 4, overlaps, skip
4	Check next activity	{start:0, finish:6}	4	[{1,4}]	0 < 4, overlaps, skip
5	Check next activity	{start:5, finish:7}	4	[{1,4}, {5,7}]	5 >= 4, select activity
6	Check next activity	{start:8, finish:9}	7	[{1,4}, {5,7}, {8,9}]	8 >= 7, select activity
7	Check next activity	{start:5, finish:9}	7	[{1,4}, {5,7}, {8,9}]	5 < 7, overlaps, skip
8	All activities checked	-	9	[{1,4}, {5,7}, {8,9}]	Done selecting maximum activities

💡 All activities checked, selection complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 6	Final
activities	[{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}]	[{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}]	[{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}]	[{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}]	[{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}]	[{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}]	[{1,4},{3,5},{0,6},{5,7},{8,9},{5,9}]
selected	[]	[]	[{1,4}]	[{1,4}]	[{1,4},{5,7}]	[{1,4},{5,7},{8,9}]	[{1,4},{5,7},{8,9}]
lastFinish	-	-	4	4	7	9	9

Key Moments - 3 Insights

Why do we sort activities by their finish time first?

Sorting by finish time ensures we always pick the activity that frees the schedule earliest, allowing more activities to fit later. See Step 1 in execution_table.

Why do we skip activities that start before the last selected activity finishes?

Because they overlap and can't be done together. For example, at Step 3, activity starting at 3 is skipped since lastFinish is 4.

Why do we always select the first activity after sorting?

Because it finishes earliest and sets the baseline for selecting subsequent non-overlapping activities. See Step 2 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the lastFinish value after selecting the activity?

A 7

B 5

C 4

D 9

💡 Hint

Check the 'lastFinish' column at Step 5 in execution_table.

At which step does the condition to select an activity fail due to overlap?

A Step 5

B Step 3

C Step 6

D Step 7

💡 Hint

Look for 'skip' actions in the Action column of execution_table.

If the activity {start: 2, finish: 3} was added, where would it be selected in the sequence?

A After the last selected activity

B Between activities at Step 2 and Step 5

C Before the first selected activity

D It would not be selected

💡 Hint

Consider sorting by finish time and the earliest finishing activity selection logic.

Concept Snapshot

Activity Selection Problem:
- Sort activities by finish time ascending
- Select first activity
- For each next activity, select if start >= last selected finish
- Skip overlapping activities
- Result: maximum number of non-overlapping activities

Full Transcript

The Activity Selection Problem involves choosing the maximum number of activities that don't overlap. We start by sorting all activities by their finish times. Then, we select the first activity because it finishes earliest. For each next activity, we check if its start time is at or after the finish time of the last selected activity. If yes, we select it; if not, we skip it. This process continues until all activities are checked. The final selection is the largest set of non-overlapping activities.

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