Activity Selection Problem in DSA Javascript

Mental Model

Choose the maximum number of activities that don't overlap by always picking the earliest finishing activity first.

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

Activities: [Start, End]
[1, 4] -> [3, 5] -> [0, 6] -> [5, 7] -> [5, 9] -> [8, 9]
↑ sorted by end time ↑

Dry Run Walkthrough

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

Goal: Select the maximum number of non-overlapping activities

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 always selected as it finishes earliest

Step 3: Skip (3,5) because it starts before (1,4) ends

Selected: (1,4)

Why: Activities overlapping with selected one are skipped

Step 4: Skip (0,6) because it overlaps with (1,4)

Selected: (1,4)

Why: Overlap means can't select this activity

Step 5: Select (5,7) because it starts after (1,4) ends

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

Why: Non-overlapping activity selected

Step 6: Skip (5,9) because it overlaps with (5,7)

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

Why: Overlap with previously selected activity

Step 7: Select (8,9) because it starts after (5,7) ends

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

Why: Non-overlapping activity selected

Result:

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

Annotated Code

DSA Javascript

class Activity {
  constructor(start, end) {
    this.start = start;
    this.end = end;
  }
}

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

  const selected = [];
  let lastEnd = -1;

  for (const activity of activities) {
    // Select activity if it starts after last selected activity 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 finish time to pick earliest finishing first

if (activity.start >= lastEnd) {

check if current activity starts after last selected ends to avoid overlap

selected.push(activity);

select current activity as it doesn't overlap

lastEnd = activity.end;

update lastEnd to current activity's finish time

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 worst case all activities can be selected and stored

vs Alternative: Naive approach tries all subsets with exponential time; greedy sorting reduces it to O(n log n)

Edge Cases

empty list of activities

returns empty selection without error

DSA Javascript

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

all activities overlap completely

only one activity is selected, the earliest finishing one

DSA Javascript

if (activity.start >= lastEnd) {

activities with same finish time

selects the first one that fits, others skipped if overlapping

DSA Javascript

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

When to Use This Pattern

When asked to schedule maximum non-overlapping intervals or tasks, use the greedy activity selection pattern by sorting on finish times.

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 start time <= last end time
Fix: Use start time >= last selected activity's end time to avoid overlap

Summary

Selects the maximum number of non-overlapping activities by always choosing the earliest finishing one.

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

The key insight is sorting activities by finish time lets you greedily pick the best next activity.

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 the largest set of activities that do not overlap in their time intervals.

2. Step 2: Clarify what is NOT the goal

   Finding the longest activity or sorting alone does not solve the problem; the focus is on maximizing non-overlapping activities.

3. Final Answer:

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

4. Quick Check:

   Maximize non-overlapping activities = Select max activities [OK]

Hint: Focus on non-overlapping activities to maximize count [OK]

Common Mistakes:

• Thinking it's about longest activity duration
• Confusing sorting with selection
• Trying to maximize total time instead of count

2. Which of the following is the correct way to sort activities by their finish time in JavaScript?

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

Solution

1. Step 1: Identify sorting key for Activity Selection

   We must sort activities by their finish time in ascending order to apply the greedy approach.

2. Step 2: Choose correct JavaScript sort syntax

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

3. Final Answer:

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

4. Quick Check:

   Sort by finish time ascending = activities.sort((a, b) => a.finish - b.finish); [OK]

Hint: Sort activities by finish time ascending for greedy selection [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Sorting finish time descending
• Sorting by duration which is irrelevant here

3. What will be the output of the following code snippet?

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

let count = 1;
let lastFinish = activities[0].finish;

for (let i = 1; i < activities.length; i++) {
  if (activities[i].start >= lastFinish) {
    count++;
    lastFinish = activities[i].finish;
  }
}
console.log(count);

medium

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Sort activities by finish time

   Sorted activities by finish time ascending: [{start:1, finish:4}, {start:3, finish:5}, {start:0, finish:6}, {start:5, finish:7}, {start:8, finish:9}, {start:5, finish:9}].

2. Step 2: Select activities greedily

   Start with first activity (finish=4). Next, select activities starting >=4: (start=5, finish=7), count=2; then (start=8, finish=9), count=3; then (start=9, finish=9) does not exist but next is (start=5, finish=9) which starts before 9, so skip. Total count is 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Greedy selection count = 4 [OK]

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

Common Mistakes:

• Not sorting activities before selection
• Counting overlapping activities
• Updating lastFinish incorrectly

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

function selectActivities(activities) {
  activities.sort((a, b) => a.start - b.start);
  let count = 1;
  let lastFinish = activities[0].finish;
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start > lastFinish) {
      count++;
      lastFinish = activities[i].finish;
    }
  }
  return count;
}

medium

A. Initialize count to 0 instead of 1

B. Comparison should be activities[i].start >= lastFinish

C. Sorting should be by finish time, not start time

D. No bug, code is correct

Solution

1. Step 1: Check sorting criteria

   The greedy approach requires sorting activities by their finish time, but the code sorts by start time, which is incorrect.

2. Step 2: Understand impact of wrong sorting

   Sorting by start time can cause wrong selection order, leading to suboptimal count of activities.

3. Final Answer:

   Sorting should be by finish time, not start time -> Option C

4. Quick Check:

   Sort by finish time for correct greedy selection [OK]

Hint: Always sort by finish time, not start time [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Using > instead of >= in condition (less critical)
• Incorrect initialization of count

5. Given the activities with start and finish times:

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

What is the maximum number of non-overlapping activities that can be selected?

hard

A. 6

B. 4

C. 5

D. 3

Solution

1. Step 1: Sort activities by finish time

   Sorted activities by finish time ascending: [{start:2, finish:3}, {start:1, finish:4}, {start:5, finish:7}, {start:6, finish:9}, {start:8, finish:10}, {start:9, finish:11}].

2. Step 2: Select activities greedily

   Select (2,3), then (5,7), then (8,10), then (9,11) overlaps with (8,10) so skip; but (6,9) overlaps with (5,7) so skip. Total count is 4.

3. Step 3: Check for more selections

   Others overlap and cannot be selected without violating non-overlap. Maximum count is 4.

4. Final Answer:

   4 -> Option B

5. Quick Check:

   Max non-overlapping activities = 4 [OK]

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

Common Mistakes:

• Not sorting activities before selection
• Selecting overlapping activities
• Ignoring start time conditions