Solving the Activity Selection Problem with Greedy Algorithms

🚀 What I Learned Today

Today, I explored one of the classic greedy algorithm problems — the Activity Selection Problem. This problem taught me how to use the greedy approach to solve scheduling tasks efficiently.

---

💡 Problem Statement

You are given a list of activities with start and end times. The goal is to select the maximum number of non-overlapping activities that a person can perform — one at a time.

---

🧠 The Greedy Strategy

To solve it:

1. Sort all activities by their end time.

2. Always pick the next activity that starts after the last selected one ends.

This strategy helps us make the best local choice at each step — and in this case, that leads to the best overall solution!

---

🧪 Python Code

def activity_selection(activities):
    # Step 1: Sort activities by end time
    activities.sort(key=lambda x: x[1])

    selected = [activities[0]]
    last_end_time = activities[0][1]

    # Step 2: Pick non-overlapping activities
    for i in range(1, len(activities)):
        start, end = activities[i]
        if start >= last_end_time:
            selected.append((start, end))
            last_end_time = end

    return selected

# Test
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print("Selected activities:", activity_selection(activities))

---

✅ Output

Selected activities: [(1, 4), (5, 7), (8, 9)]

---

🎯 What I Gained

• Learned how sorting by end time can lead to an optimal greedy solution.

• Understood the importance of picking the right local decision.

• Saw how simple logic can solve a real-world problem efficiently!

---

That wraps up what I learned today using Python and greedy thinking. 🚀
Next up: More greedy problems and real-world applications!