Introduction

The Activity Selection Problem is one of the most important problems in Data Structures and Algorithms (DSA) and is a classic example of a greedy algorithm. If you are enrolled in a DSA course in Jaipur, mastering this problem will help you understand how greedy strategies work in scheduling and optimization problems.

This problem demonstrates how selecting locally optimal choices leads to a globally optimal solution.

What is Activity Selection Problem?

You are given:

• A set of activities
• Each activity has a start time and finish time

Goal:

• Select the maximum number of activities
• Ensure no two activities overlap

Example

Activities:
Start: [1, 3, 0, 5, 8, 5]
Finish: [2, 4, 6, 7, 9, 9]

Optimal selection:

• (1,2), (3,4), (5,7), (8,9)

Total activities = 4

Greedy Strategy

• Always select the activity that finishes earliest
• This leaves maximum time for remaining activities

Algorithm Steps

1. Sort activities based on finish time
2. Select the first activity
3. For each next activity:
   • If start time ≥ last selected finish time → select it
4. Continue until all activities are processed

Time Complexity

O(n log⁡ n)

• Sorting → O(n log n)
• Selection → O(n)

Why Greedy Works Here

• Selecting earliest finishing activity gives more room
• Ensures maximum number of non-overlapping activities

Real-World Applications

• Meeting room scheduling
• CPU task scheduling
• Event planning
• Resource allocation

Advantages

• Simple and efficient
• Optimal solution guaranteed
• Easy to implement

Limitations

• Works only for specific problems
• Requires sorting
• Not applicable everywhere

Common Interview Questions

• Maximum number of meetings
• Scheduling problems
• Job sequencing
• Interval problems

Best Practices

• Always sort by finish time
• Validate overlapping conditions
• Understand greedy choice proof
• Practice interval problems

Summary

• Activity selection is a greedy problem
• Select activities with earliest finish time
• Time complexity is O(n log n)
• Widely used in scheduling problems
• Important for coding interviews

FAQs

Q1. What is activity selection problem?
It is selecting maximum non-overlapping activities.

Q2. Why do we sort by finish time?
To maximize remaining time for other activities.

Q3. What is the time complexity?
O(n log n).

Q4. Is greedy always optimal here?
Yes, for this problem.

Q5. Is it important for interviews?
Yes, it is a classic greedy problem.

Internal Link

To explore more programming and development courses, click here for more free courses.