Activity Selection Problem in DSA Typescript - 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

↓

Done

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

Execution Sample

DSA Typescript

interface Activity {
  start: number;
  finish: number;
}

function selectActivities(activities: Activity[]): Activity[] {
  activities.sort((a, b) => a.finish - b.finish);
  const selected: Activity[] = [];
  let lastFinish = 0;
  for (const act of activities) {
    if (act.start >= lastFinish) {
      selected.push(act);
      lastFinish = act.finish;
    }
  }
  return selected;
}

This code sorts activities by finish time and selects the maximum number of non-overlapping activities.

Execution Table

Step	Operation	Current Activity (start, finish)	Last Selected Finish	Selected Activities	Action	Visual State
1	Sort activities by finish time	-	-	[]	Sorted activities	[ (1,4), (3,5), (0,6), (5,7), (8,9), (5,9) ]
2	Select first activity	(1,4)	0	[]	Select (1,4)	[(1,4)]
3	Check next activity	(3,5)	4	[(1,4)]	Skip (3,5) because 3 < 4	[(1,4)]
4	Check next activity	(0,6)	4	[(1,4)]	Skip (0,6) because 0 < 4	[(1,4)]
5	Check next activity	(5,7)	4	[(1,4)]	Select (5,7) because 5 >= 4	[(1,4), (5,7)]
6	Check next activity	(8,9)	7	[(1,4), (5,7)]	Select (8,9) because 8 >= 7	[(1,4), (5,7), (8,9)]
7	Check next activity	(5,9)	9	[(1,4), (5,7), (8,9)]	Skip (5,9) because 5 < 9	[(1,4), (5,7), (8,9)]
8	End of activities	-	9	[(1,4), (5,7), (8,9)]	Done selecting	[(1,4), (5,7), (8,9)]

💡 All activities checked; selection complete.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
lastFinish	0	4	4	4	7	9	9	9
selected	[]	[(1,4)]	[(1,4)]	[(1,4)]	[(1,4), (5,7)]	[(1,4), (5,7), (8,9)]	[(1,4), (5,7), (8,9)]	[(1,4), (5,7), (8,9)]
currentActivity	-	(1,4)	(3,5)	(0,6)	(5,7)	(8,9)	(5,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 up time earliest, allowing more activities to fit later. See Step 1 in execution_table where activities are sorted.

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 and 4, activities starting before lastFinish are skipped to avoid overlap.

Why do we update lastFinish only when we select an activity?

Because lastFinish marks the end time of the last chosen activity, helping to check overlap for future activities. See variable_tracker for lastFinish updates after selection steps.

Visual Quiz - 3 Questions

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

A 4

B 7

C 5

D 9

💡 Hint

Check the 'Last Selected Finish' column at Step 5 in execution_table.

At which step does the condition 'act.start >= lastFinish' become false for the first time?

A Step 3

B Step 2

C Step 5

D Step 6

💡 Hint

Look at the 'Action' column in execution_table where activities are skipped due to overlap.

If the activity (3,5) was changed to (4,5), how would the selection change at Step 3?

A It would cause an error

B It would still be skipped

C It would be selected instead of skipped

D It would be selected but lastFinish would not update

💡 Hint

Compare 'currentActivity' start time with 'lastFinish' at Step 3 in variable_tracker.

Concept Snapshot

Activity Selection Problem:
- Sort activities by finish time
- Select first activity
- For each next activity, select if start >= last selected finish
- Update last selected finish time
- Result: maximum set 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 activities by their finish times. Then, we pick the first activity and keep track of its finish time. For each next activity, if its start time is equal or after the last selected finish time, we select it and update the finish time. Otherwise, we skip it. This process continues until all activities are checked. The final selected list contains the maximum number of compatible 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 activities that do not overlap and maximize the count.

2. Step 2: Identify the correct objective

   Among the options, only selecting the maximum number of non-overlapping activities matches the problem's goal.

3. Final Answer:

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

4. Quick Check:

   Goal = Max non-overlapping activities [OK]

Hint: Focus on maximizing count without time conflicts [OK]

Common Mistakes:

• Confusing longest duration with maximum count
• Sorting by start time only
• Summing all activity durations

2. Which of the following TypeScript code snippets correctly sorts activities by their finish time for the Activity Selection Problem?

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) => b.start - a.start);

Solution

1. Step 1: Identify sorting criteria for Activity Selection

   Activities must be sorted by their finish times in ascending order to apply the greedy approach.

2. Step 2: Match sorting code to criteria

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

3. Final Answer:

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

4. Quick Check:

   Sort by finish time ascending [OK]

Hint: Sort activities by finish time ascending [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Sorting finish time descending
• Using incorrect comparison operators

3. What is the output of the following TypeScript code for the Activity Selection Problem?

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);

const selected = [];
let lastFinish = 0;
for (const activity of activities) {
  if (activity.start >= lastFinish) {
    selected.push(activity);
    lastFinish = activity.finish;
  }
}

console.log(selected);

medium

A. [{start:0, finish:6}, {start:8, finish:9}]

B. [{start:1, finish:4}, {start:3, finish:5}, {start:5, finish:7}]

C. [{start:1, finish:4}, {start:5, finish:7}, {start:8, finish:9}]

D. [{start:3, finish:5}, {start:5, finish:9}]

Solution

1. Step 1: Sort activities by finish time

   Sorted list: [{1,4}, {3,5}, {0,6}, {5,7}, {8,9}, {5,9}]

2. Step 2: Select activities greedily

   Select {1,4} (start 1 >= 0), then {5,7} (start 5 >= 4), then {8,9} (start 8 >= 7). Others overlap.

3. Final Answer:

   [{start:1, finish:4}, {start:5, finish:7}, {start:8, finish:9}] -> Option C

4. Quick Check:

   Greedy selection = chosen activities [OK]

Hint: Pick earliest finishing activities first [OK]

Common Mistakes:

• Selecting overlapping activities
• Not sorting by finish time
• Updating lastFinish incorrectly

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

const activities = [
  {start: 1, finish: 3},
  {start: 2, finish: 5},
  {start: 4, finish: 7}
];

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

const selected = [];
let lastFinish = 0;
for (const activity of activities) {
  if (activity.start >= lastFinish) {
    selected.push(activity);
    lastFinish = activity.finish;
  }
}

console.log(selected);

medium

A. Not initializing selected array

B. Sorting by start time instead of finish time

C. Using 'let' instead of 'const' for lastFinish

D. Incorrect comparison operator in if condition

Solution

1. Step 1: Check sorting criteria

   The code sorts activities by start time, but the greedy algorithm requires sorting by finish time.

2. Step 2: Identify impact of sorting error

   Sorting by start time can cause incorrect selection of overlapping activities, breaking the algorithm.

3. Final Answer:

   Sorting by start time instead of finish time -> Option B

4. Quick Check:

   Sort by finish time needed [OK]

Hint: Always sort by finish time for this problem [OK]

Common Mistakes:

• Sorting by start time
• Confusing variable declarations
• Wrong if condition operators

5. Given the activities with start and finish times:

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

How many activities can be selected using the Activity Selection Problem's greedy approach, and which are they?

hard

A. 4 activities: {0,3}, {3,5}, {5,9}, {8,10}

B. 4 activities: {0,3}, {3,5}, {4,7}, {8,10}

C. 5 activities: {0,3}, {1,4}, {3,5}, {4,7}, {8,10}

D. 3 activities: {0,3}, {3,5}, {5,9}

Solution

1. Step 1: Sort activities by finish time

   Sorted: [{0,3}, {1,4}, {3,5}, {4,7}, {5,9}, {8,10}]

2. Step 2: Select greedily

   {0,3} (last=3); skip {1,4}; {3,5} (last=5); {4,7} overlaps with {3,5} so skip; {5,9} (last=9); {8,10} overlaps with {5,9} so skip. Actually, {8,10} starts before 9, so overlaps. So selected are {0,3}, {3,5}, {5,9} only 3 activities.

3. Final Answer:

   3 activities: {0,3}, {3,5}, {5,9} -> Option D

4. Quick Check:

   Greedy picks non-overlapping max activities [OK]

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

Common Mistakes:

• Selecting overlapping activities
• Miscounting due to off-by-one errors
• Ignoring sorting step