Why Activity Selection Problem in DSA Typescript?

The Big Idea

What if you could instantly know the best schedule to fit the most activities without any clashes?

The Scenario

Imagine you have a list of meetings to attend in one day, but some meetings overlap in time. You want to attend as many meetings as possible without any clashes.

The Problem

Trying to pick meetings manually means checking every meeting against all others to avoid overlaps. This is slow and confusing, especially with many meetings, and easy to make mistakes.

The Solution

The Activity Selection Problem uses a smart way to pick meetings by sorting them by their finish times and always choosing the earliest finishing meeting next. This ensures you attend the maximum number of meetings without conflicts.

Before vs After

✗ Before

const meetings = [[1,4],[3,5],[0,6],[5,7]];
function overlaps(a: number[], b: number[]): boolean {
  return a[0] < b[1] && b[0] < a[1];
}
// Manually check each meeting against others for overlaps
let count = 0;
for(let i=0; i<meetings.length; i++) {
  let canAttend = true;
  for(let j=0; j<meetings.length; j++) {
    if(i !== j && overlaps(meetings[i], meetings[j])) {
      canAttend = false;
      break;
    }
  }
  if(canAttend) count++;
}

✓ After

const meetings = [[1,4],[3,5],[0,6],[5,7]];
meetings.sort((a,b) => a[1] - b[1]);
let count = 1;
let lastFinish = meetings[0][1];
for(let i=1; i<meetings.length; i++) {
  if(meetings[i][0] >= lastFinish) {
    count++;
    lastFinish = meetings[i][1];
  }
}

What It Enables

This approach lets you quickly find the largest number of non-overlapping activities you can do, saving time and avoiding confusion.

Real Life Example

Scheduling conference talks to attend the most sessions without missing any due to time clashes.

Key Takeaways

Manual checking of overlapping activities is slow and error-prone.

Sorting activities by finish time helps pick the maximum number efficiently.

The greedy method ensures the best schedule without conflicts.