Activity Selection Problem in DSA Typescript - Deep Dive

Overview - Activity Selection Problem

What is it?

The Activity Selection Problem is about choosing the maximum number of activities that don't overlap in time. Each activity has a start time and an end time. The goal is to select activities so that no two chosen activities happen at the same time. This helps in scheduling tasks efficiently.

Why it matters

Without this problem's solution, scheduling tasks or events would be inefficient, leading to wasted time or resources. For example, if you book overlapping meetings, you can't attend all. Solving this problem helps in planning where time is limited and many tasks compete for it.

Where it fits

Before learning this, you should understand arrays and sorting basics. After this, you can explore more complex scheduling problems like interval graphs or dynamic programming approaches to scheduling.

Mental Model

Core Idea

Pick activities that finish earliest to leave room for more activities later.

Think of it like...

Imagine you have a single meeting room and many people want to use it. To fit the most meetings, you always let the meeting that ends soonest happen first, then pick the next meeting that starts after it ends, and so on.

Activities sorted by finish time:

Start:  | 1 | 3 | 0 | 5 | 8 | 5 |
Finish: | 2 | 4 | 6 | 7 | 9 | 9 |

Selection process:
[1-2] -> [3-4] -> [5-7] -> [8-9]

Diagram:
┌─────────┐
│ Activity│
├─────────┤
│ 1 - 2   │
│ 3 - 4   │
│ 5 - 7   │
│ 8 - 9   │
└─────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Activities and Time Slots

Concept: Introduce what activities are and how start and end times define them.

An activity is a task with a start time and an end time. For example, Activity A starts at 1 and ends at 2. Activities can overlap if one starts before another ends. We want to find which activities can fit without overlapping.

Result

You understand that activities are intervals on a timeline and overlapping means two intervals share some time.

Understanding activities as time intervals is key to seeing why some can't happen together.

2

Foundation

Sorting Activities by Finish Time

Concept: Sorting activities by their end times helps in making the best choices.

Given a list of activities, we sort them so the one that finishes earliest comes first. For example, activities [(1,2), (3,4), (0,6)] become [(1,2), (3,4), (0,6)] after sorting by finish time 2,4,6.

Result

Activities are ordered to consider earliest finishing ones first.

Sorting by finish time sets the stage for a greedy choice that leads to the best overall schedule.

3

Intermediate

Greedy Choice: Selecting Earliest Finishing Activity

🤔Before reading on: Do you think picking the longest activity first or the earliest finishing activity first leads to more total activities? Commit to your answer.

Concept: Choosing the activity that finishes earliest leaves the most room for others.

Start with the first activity in the sorted list (earliest finish). Then pick the next activity that starts after the last selected activity ends. Repeat until no more activities fit.

Result

Selected activities maximize the number of non-overlapping tasks.

Choosing earliest finishing activities is a simple rule that guarantees the maximum number of activities.

4

Intermediate

Implementing Activity Selection in TypeScript

🤔Before reading on: Will a simple loop checking start and end times suffice to select activities? Commit to your answer.

Concept: Use a loop to pick activities based on sorted finish times and start times.

Code example: function selectActivities(start: number[], finish: number[]): number[] { const n = start.length; const activities = start.map((s, i) => ({start: s, finish: finish[i], index: i})); activities.sort((a, b) => a.finish - b.finish); const selected: number[] = []; let lastFinish = -1; for (const activity of activities) { if (activity.start >= lastFinish) { selected.push(activity.index); lastFinish = activity.finish; } } return selected; } This picks the maximum set of activities without overlap.

Result

The function returns indices of selected activities maximizing count.

A simple loop with sorted activities efficiently solves the problem.

5

Intermediate

Dry Run Example with Sample Activities

🤔Before reading on: How many activities do you think can be selected from [(1,2), (3,4), (0,6), (5,7), (8,9), (5,9)]? Commit to your answer.

Concept: Walk through the algorithm step-by-step with real data.

Activities: Index Start Finish 0 1 2 1 3 4 2 0 6 3 5 7 4 8 9 5 5 9 Sorted by finish: 0(1,2), 1(3,4), 2(0,6), 3(5,7), 4(8,9), 5(5,9) Selection: Pick 0 (1,2) Next start >= 2: pick 1 (3,4) Next start >= 4: skip 2 (0,6), pick 3 (5,7) Next start >= 7: pick 4 (8,9) Skip 5 (5,9) because it overlaps Selected indices: [0,1,3,4]

Result

Four activities selected: indices 0,1,3,4.

Step-by-step tracing confirms the greedy method picks the maximum activities.

6

Advanced

Handling Edge Cases and Equal Finish Times

🤔Before reading on: If two activities finish at the same time, does picking either first affect the maximum count? Commit to your answer.

Concept: Understand how ties in finish times affect selection and how to handle them.

If two activities finish at the same time, picking either first does not reduce the maximum count. The algorithm can pick any of them as long as start times don't overlap. To keep consistency, stable sorting or tie-breakers by start time can be used.

Result

Algorithm remains correct even with equal finish times.

Knowing tie handling prevents bugs in real data with equal finish times.

7

Expert

Extending to Weighted Activity Selection Problem

🤔Before reading on: Does the greedy earliest finish time approach work if activities have different values or weights? Commit to your answer.

Concept: When activities have weights (values), the problem needs a different approach than greedy.

The weighted activity selection problem requires dynamic programming because picking earliest finishing activity may not maximize total weight. Instead, we consider all compatible activities and choose the best combination by comparing sums of weights.

Result

Greedy fails for weighted case; dynamic programming is needed.

Recognizing limits of greedy approach guides choosing correct algorithms for complex scheduling.

Under the Hood

The algorithm sorts activities by their finish times, then iterates through them once. It keeps track of the last selected activity's finish time and picks the next activity only if it starts after or exactly when the last one finished. This greedy choice ensures no overlaps and maximizes count because choosing earliest finishing activity leaves maximum room for others.

Why designed this way?

This approach was designed to solve scheduling efficiently without checking all subsets, which would be slow. Sorting and greedy selection reduce complexity from exponential to O(n log n) due to sorting. Alternatives like brute force were too slow for large inputs.

┌─────────────┐
│ Activities  │
│ (start,end) │
└─────┬───────┘
      │ Sort by finish time
      ▼
┌─────────────┐
│ Sorted list │
└─────┬───────┘
      │ Iterate and select
      ▼
┌─────────────┐
│ Selected    │
│ activities  │
└─────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does picking the longest activity first always maximize the number of activities? Commit yes or no.

Common Belief: Picking the longest activity first will maximize the number of activities scheduled.

Reality: Picking the longest activity first often reduces the total number of activities because it blocks more time, leaving less room for others.

Why it matters: Choosing longest activities first can lead to fewer tasks done, wasting available time.

Quick: Can the greedy earliest finish time method solve weighted activity selection? Commit yes or no.

Common Belief: The greedy earliest finish time method works for all activity selection problems, including weighted ones.

Reality: Greedy earliest finish time fails for weighted problems; dynamic programming is required to maximize total weight.

Why it matters: Using greedy for weighted cases leads to suboptimal schedules and lost value.

Quick: If two activities have the same finish time, does the order of selection affect the maximum count? Commit yes or no.

Common Belief: The order of activities with the same finish time affects the maximum number of activities selected.

Reality: The order does not affect the maximum count as long as the selection respects start times; any order works.

Why it matters: Worrying about tie order can complicate implementation unnecessarily.

Expert Zone

1

The greedy algorithm's correctness depends on the problem's optimal substructure and greedy choice properties, which are subtle and not always present in similar problems.

2

Stable sorting by finish time and then by start time can help maintain predictable selection order, which is useful in debugging and reproducibility.

3

In real systems, activities may have constraints beyond time (like resources), requiring extensions beyond the classic problem.

When NOT to use

Do not use this greedy approach when activities have weights or values; instead, use dynamic programming. Also avoid it when activities have complex constraints like multiple resources or dependencies.

Production Patterns

Used in scheduling meetings, CPU job scheduling, booking systems, and event planning where maximizing non-overlapping tasks is critical. Often combined with priority queues or interval trees for dynamic updates.

Connections

Interval Scheduling

Activity Selection is a classic example of interval scheduling problems.

Understanding activity selection helps grasp broader interval scheduling challenges in operating systems and networking.

Dynamic Programming

Weighted Activity Selection extends the problem requiring dynamic programming instead of greedy.

Knowing when greedy fails and DP is needed sharpens algorithm choice skills.

Project Management

Scheduling tasks without overlap is a core challenge in project management.

Algorithms like activity selection underpin tools that optimize resource and time allocation in projects.

Common Pitfalls

#1 Selecting activities based on earliest start time instead of earliest finish time.

Wrong approach:

activities.sort((a, b) => a.start - b.start);
// Then select activities greedily by start time

Correct approach:

activities.sort((a, b) => a.finish - b.finish);
// Then select activities greedily by finish time

Root cause:

Misunderstanding that earliest start does not guarantee maximum number of activities.

#2 Trying to select overlapping activities by ignoring finish times.

Wrong approach:

for (const activity of activities) {
selected.push(activity.index); // no check for overlap
}

Correct approach:

let lastFinish = -1;
for (const activity of activities) {
if (activity.start >= lastFinish) {
selected.push(activity.index);
lastFinish = activity.finish;
}
}

Root cause:

Ignoring the core constraint of non-overlapping intervals.

#3 Using greedy approach for weighted activities expecting maximum total weight.

Wrong approach:

Select activities greedily by earliest finish time ignoring weights.

Correct approach:

Use dynamic programming to consider weights and compatibility of activities.

Root cause:

Assuming greedy works for all variations of activity selection.

Key Takeaways

The Activity Selection Problem finds the maximum number of non-overlapping activities by always choosing the earliest finishing activity first.

Sorting activities by their finish times is essential to apply the greedy selection correctly and efficiently.

Greedy selection works because choosing the earliest finishing activity leaves the most room for others, maximizing total count.

This approach runs in O(n log n) time due to sorting, making it efficient for large inputs.

For weighted activities, greedy fails and dynamic programming is required to maximize total value.

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