Data Structures and Algorithms: Activity Selection Problem

Welcome to this engaging lesson on Data Structures and Algorithms! Today, we'll be diving into the fascinating world of the Activity Selection Problem. This problem is a common topic in competitive programming and has practical applications in scheduling events, task assignment, and more.

Understanding the Activity Selection Problem 📝

The Activity Selection Problem involves selecting the maximum number of non-overlapping activities from a list of given activities. Each activity has a specific starting and ending time. The goal is to choose the activities such that no two activities overlap (i.e., the ending time of one activity is earlier than the starting time of the next one).

Real-world Applications 🎯

Imagine organizing a conference with multiple workshops happening simultaneously. Each workshop has a defined start and end time. The goal is to select the maximum number of workshops that do not clash with each other, ensuring that attendees can participate in as many sessions as possible.

Algorithm Explanation 💡

The solution to the Activity Selection Problem can be achieved using the Greedy Algorithm. Here's how it works:

Sort the activities in increasing order of their starting times.
Initialize an empty list to store the selected activities.
Iterate through the sorted list of activities.
At each iteration, check if the ending time of the current activity is later than the starting time of the last activity in the selected list. If it is, add the current activity to the selected list.

Let's walk through an example:

markdown

Activities:
(1, 3)
(2, 4)
(3, 5)
(0, 5)
(0, 6)
(3, 7)

Sorted Activities:
(0, 5)
(0, 6)
(1, 3)
(2, 4)
(3, 5)
(3, 7)

Selected Activities:
(0, 5)
(3, 7)

In this example, we first sorted the activities and then iterated through them, selecting the activities that did not overlap with the ones already selected. The selected activities are (0, 5) and (3, 7).

Implementation in Python 💻

Here's a Python implementation of the Activity Selection Algorithm:

python

def activity_selection(activities):
    # Sort the activities by their starting times
    activities.sort(key=lambda x: x[0])

    selected_activities = []
    current_end_time = -float('inf')

    for activity in activities:
        start, end = activity

        # Check if the current end time is less than the start time of the current activity
        if start > current_end_time:
            # If so, add the activity to the selected list and update the current end time
            selected_activities.append(activity)
            current_end_time = end

    return selected_activities

# Test the function with some example activities
activities = [(1, 3), (2, 4), (3, 5), (0, 5), (0, 6), (3, 7)]
selected_activities = activity_selection(activities)
print(selected_activities)  # Output: [(0, 5), (3, 7)]

Data Structures and Algorithms: Activity Selection Problem

Data Structures and Algorithms: Activity Selection Problem

Understanding the Activity Selection Problem 📝

Real-world Applications 🎯

Algorithm Explanation 💡

Implementation in Python 💻

Quiz Time 🧩