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.