Activity Selection Problem in DSA Typescript

Mental Model

Choose the most activities that don't overlap by always picking the one that finishes earliest.

Analogy: Imagine you have a single meeting room and many meetings to schedule. To fit the most meetings, always pick the meeting that ends soonest so the room becomes free quickly for the next meeting.

Activities (start, end):
[1, 4]  [3, 5]  [0, 6]  [5, 7]  [8, 9]  [5, 9]
Timeline: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Selected activities: [1,4] -> [5,7] -> [8,9]

Dry Run Walkthrough

Input: activities: [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)]

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

Step 1: Sort activities by their finish time

[(1,4), (3,5), (0,6), (5,7), (5,9), (8,9)]

Why: Sorting by finish time helps pick the earliest finishing activity first.

Step 2: Select first activity (1,4)

Selected: [(1,4)]

Why: First activity finishes earliest, so we pick it.

Step 3: Check next activity (3,5), skip because it starts before last selected ends

Selected: [(1,4)]

Why: Activity (3,5) overlaps with (1,4), so skip.

Step 4: Check next activity (0,6), skip because it overlaps

Selected: [(1,4)]

Why: Activity (0,6) overlaps with (1,4), so skip.

Step 5: Check next activity (5,7), select because it starts after last selected ends

Selected: [(1,4), (5,7)]

Why: No overlap, so select.

Step 6: Check next activity (5,9), skip because it overlaps with (5,7)

Selected: [(1,4), (5,7)]

Why: Starts at same time as (5,7), overlaps, so skip.

Step 7: Check next activity (8,9), select because it starts after last selected ends

Selected: [(1,4), (5,7), (8,9)]

Why: No overlap, so select.

Result:

Selected activities: (1,4) -> (5,7) -> (8,9)

Annotated Code

DSA Typescript

class Activity {
  constructor(public start: number, public end: number) {}
}

function activitySelection(activities: Activity[]): Activity[] {
  // Sort activities by their finish time
  activities.sort((a, b) => a.end - b.end);

  const selected: Activity[] = [];
  let lastEnd = 0;

  for (const activity of activities) {
    // Select activity if it starts after last selected ends
    if (activity.start >= lastEnd) {
      selected.push(activity);
      lastEnd = activity.end;
    }
  }

  return selected;
}

// Driver code
const activities = [
  new Activity(1, 4),
  new Activity(3, 5),
  new Activity(0, 6),
  new Activity(5, 7),
  new Activity(8, 9),
  new Activity(5, 9),
];

const result = activitySelection(activities);
for (const act of result) {
  console.log(`(${act.start},${act.end})`);
}

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

Sort activities by earliest finish time to prioritize.

if (activity.start >= lastEnd) {

Check if current activity starts after last selected activity ends.

selected.push(activity);

Add current activity to the selected list.

lastEnd = activity.end;

Update the end time to the current activity's end.

Output

(1,4)

(5,7)

(8,9)

Complexity Analysis

Time: O(n log n) because sorting the activities by finish time dominates the runtime.

Space: O(n) because in the worst case all activities can be selected and stored.

vs Alternative: A naive approach checking all subsets would be exponential O(2^n), so this greedy method is much faster.

Edge Cases

No activities

Returns empty list, no activities selected.

DSA Typescript

for (const activity of activities) {

All activities overlap

Only one activity (the earliest finishing) is selected.

DSA Typescript

if (activity.start >= lastEnd) {

Activities with same start and end times

Selects the first one after sorting, skips others due to overlap.

DSA Typescript

if (activity.start >= lastEnd) {

When to Use This Pattern

When asked to schedule the maximum number of non-overlapping intervals or tasks, reach for the greedy Activity Selection pattern because sorting by finish time ensures optimal selection.

Common Mistakes

Mistake: Sorting activities by start time instead of finish time.
Fix: Sort activities by their finish time to ensure earliest finishing activities are chosen first.

Mistake: Selecting activities that overlap by checking only start times without updating last selected end time.
Fix: Always update the last selected activity's end time after selection to correctly check overlaps.

Summary

Selects the maximum number of activities that don't overlap by always choosing the earliest finishing activity next.

Use when you need to schedule the most tasks or events without conflicts in time.

The key insight is sorting by finish time lets you greedily pick the best next activity to maximize total count.

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