Activity Selection Problem in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Activity Selection Greedy Algorithm

What is the output of the following TypeScript code that selects the maximum number of non-overlapping activities?

DSA Typescript

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

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

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

const result = activitySelection(activities);
console.log(result.map(a => `[${a.start},${a.finish}]`).join(' -> '));

A [0,6] -> [5,7] -> [8,9]

B [1,4] -> [5,7] -> [8,9]

C [1,4] -> [3,5] -> [5,7] -> [8,9]

D [3,5] -> [5,7] -> [8,9]

💡 Hint

Sort activities by their finish time and pick the earliest finishing activity that starts after the last selected one.

The greedy algorithm sorts activities by finish time and selects the earliest finishing activities that do not overlap. The selected activities are [1,4], [5,7], and [8,9].

🧠 Conceptual

intermediate

Maximum Number of Activities Selected

Given the activities with start and finish times: (1,3), (2,5), (4,7), (6,9), (8,10), how many activities can be selected without overlap using the greedy approach?

A 3

B 4

C 2

D 5

💡 Hint

Sort by finish time and pick activities that start after the last selected finish time.

Sorting by finish time: (1,3), (2,5), (4,7), (6,9), (8,10). Select (1,3), then (4,7), skip (6,9) because 6 < 7, then (8,10). So maximum is 3.

🔧 Debug

advanced

Identify the Bug in Activity Selection Code

What error does the following TypeScript code produce when run?

DSA Typescript

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

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

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

const result = activitySelection(activities);
console.log(result.map(a => `[${a.start},${a.finish}]`).join(' -> '));

A No error, outputs '[1,4] -> [5,7] -> [8,9]'

B No error, outputs '[1,4] -> [3,5] -> [5,7] -> [8,9]'

C No error, outputs '[0,6] -> [8,9]'

D No error, outputs '[0,6] -> [5,7] -> [8,9]'

💡 Hint

Check how activities are sorted before selection.

The code sorts activities by start time instead of finish time, which breaks the greedy approach. It selects activities starting earliest but may overlap. The output is '[0,6] -> [8,9]'.

🚀 Application

advanced

Find Selected Activities for Given Intervals

Given these activities: (2,4), (3,5), (1,3), (5,7), (6,8), (8,10), which activities will be selected by the greedy algorithm that sorts by finish time?

A (1,3), (3,5), (5,7), (8,10)

B (1,3), (2,4), (5,7), (8,10)

C (2,4), (5,7), (6,8), (8,10)

D (1,3), (5,7), (8,10)

💡 Hint

Sort activities by finish time and pick earliest finishing compatible activities.

Sorted by finish time: (1,3), (2,4), (3,5), (5,7), (6,8), (8,10). Select (1,3), skip (2,4) because 2 < 3, select (3,5) because 3 >= 3, select (5,7) because 5 >= 5, skip (6,8) because 6 < 7, select (8,10).

🧠 Conceptual

expert

Why Sorting by Finish Time is Optimal in Activity Selection

Why does sorting activities by their finish time guarantee the maximum number of non-overlapping activities selected?

A Because sorting by finish time ensures activities are selected in the order they were added.

B Because sorting by start time always selects the longest activities first.

C Because sorting by finish time minimizes the total duration of selected activities.

D Because selecting the earliest finishing activity leaves maximum room for remaining activities.

💡 Hint

Think about how choosing the earliest finishing activity affects the remaining time.

Choosing the activity that finishes earliest leaves the largest possible time for the rest of the activities, maximizing the total number selected.

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