Activity Selection Problem in DSA Typescript - Build from Scratch

Activity Selection Problem

📖 Scenario: You are organizing a conference with many talks. Each talk has a start time and an end time. You want to attend the maximum number of talks without any overlaps.

🎯 Goal: Build a program that selects the maximum number of non-overlapping activities (talks) you can attend.

📋 What You'll Learn

Create an array of activities with start and end times

Sort activities by their end times

Select the maximum number of activities that do not overlap

Print the selected activities in order

💡 Why This Matters

🌍 Real World

Scheduling talks, meetings, or tasks to maximize usage of time without conflicts.

💼 Career

Useful for roles in project management, event planning, and software development involving scheduling algorithms.

1

Create the list of activities

Create an array called activities with these exact objects: { start: 1, end: 4 }, { start: 3, end: 5 }, { start: 0, end: 6 }, { start: 5, end: 7 }, { start: 8, end: 9 }, { start: 5, end: 9 }

DSA Typescript

// Your code here

Hint

Use an array of objects with start and end properties.

2

Sort activities by their end time

Create a new array called sortedActivities by sorting activities in ascending order of their end property using activities.slice().sort((a, b) => a.end - b.end)

DSA Typescript

const activities = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
  { start: 5, end: 9 }
];
// Your code here

Hint

Use slice() to copy the array before sorting to keep original intact.

3

Select maximum number of non-overlapping activities

Create an array called selectedActivities and add the first activity from sortedActivities. Then use a for loop with variable i from 1 to sortedActivities.length. Inside the loop, if sortedActivities[i].start is greater or equal to the end of the last selected activity, add sortedActivities[i] to selectedActivities

DSA Typescript

const activities = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
  { start: 5, end: 9 }
];

const sortedActivities = activities.slice().sort((a, b) => a.end - b.end);
// Your code here

Hint

Start with the first activity and add others only if they start after the last selected activity ends.

4

Print the selected activities

Use console.log to print the selectedActivities array

DSA Typescript

const activities = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
  { start: 5, end: 9 }
];

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

const selectedActivities = [sortedActivities[0]];

for (let i = 1; i = selectedActivities[selectedActivities.length - 1].end) {
    selectedActivities.push(sortedActivities[i]);
  }
}
// Your code here

Hint

Print the selectedActivities array to see the chosen talks.