Activity Selection Problem#

Welcome to Day 41 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deep into the Activity Selection Problem, a classic example of how greedy algorithms can be used to solve optimization problems efficiently.

What is the Activity Selection Problem?#

The Activity Selection Problem involves selecting the maximum number of non-overlapping activities that can be performed by a single person or machine, given a set of activities with their start and finish times.

Problem Statement#

Given n activities with their start and finish times, select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

Greedy Approach#

The greedy approach to solve this problem is to always pick the next activity with the earliest finish time. This approach works because choosing the activity with the earliest finish time leaves more room for other activities.

Implementation#

Let’s implement the Activity Selection Problem using Python:

 1def activity_selection(start, finish):
 2    n = len(start)
 3    
 4    # Sort activities by finish time
 5    activities = sorted(zip(start, finish), key=lambda x: x[1])
 6    
 7    selected = [0]  # First activity is always selected
 8    last_finish = activities[0][1]
 9    
10    for i in range(1, n):
11        if activities[i][0] >= last_finish:
12            selected.append(i)
13            last_finish = activities[i][1]
14    
15    return selected
16
17# Example usage
18start = [1, 3, 0, 5, 8, 5]
19finish = [2, 4, 6, 7, 9, 9]
20selected = activity_selection(start, finish)
21print("Selected activities:", selected)
22
23# Print detailed schedule
24print("\nDetailed Schedule:")
25for i in selected:
26    print(f"Activity {i}: Start time = {start[i]}, Finish time = {finish[i]}")

Time Complexity#

• Sorting the activities: O(n log n)
• Selecting activities: O(n)

Overall time complexity: O(n log n), where n is the number of activities.

Space Complexity#

O(n) to store the sorted list of activities.

Proof of Correctness#

The greedy choice property holds for this problem because:

1. Choosing the activity with the earliest finish time is always safe.
2. After choosing an activity, the subproblem we’re left with is of the same type.

Variations of the Problem#

1. Weighted Activity Selection: Each activity has a weight or value, and the goal is to maximize the total value.
2. Multiple Resource Activity Selection: Multiple people or machines are available to perform activities.
3. Activity Selection with Deadlines: Each activity has a deadline, and the goal is to schedule as many activities as possible before their deadlines.

Real-world Applications#

1. Scheduling classes in a classroom
2. Managing meeting rooms in an office
3. Allocating tasks to a single processor
4. TV program scheduling

Exercise#

1. Modify the algorithm to handle the case where activities are not sorted by finish time initially.
2. Implement the Weighted Activity Selection Problem using dynamic programming.
3. Solve the Activity Selection Problem when activities have deadlines and penalties for missing the deadlines.

Summary#

Today, we explored the Activity Selection Problem, a classic example of how greedy algorithms can efficiently solve certain types of optimization problems. We implemented a solution, discussed its time and space complexity, and looked at variations and real-world applications of the problem.

Understanding the Activity Selection Problem and its solutions provides valuable insights into greedy algorithms and their applications in scheduling and resource allocation problems.

Tomorrow, we’ll dive into another fundamental greedy algorithm: Huffman Coding for data compression. Stay tuned!

Solution#

 1import bisect
 2
 3def weighted_activity_selection(start, finish, value):
 4    # Sort activities by finish time
 5    jobs = sorted(zip(start, finish, value), key=lambda x: x[1])
 6    starts = [j[0] for j in jobs]
 7    finishes = [j[1] for j in jobs]
 8    n = len(jobs)
 9
10    # dp[i] = best value using the first i jobs (1-indexed)
11    dp = [0] * (n + 1)
12    for i in range(1, n + 1):
13        s, f, v = jobs[i-1]
14        # Find the last job that finishes at or before this job's start
15        p = bisect.bisect_right(finishes, s, 0, i - 1)
16        dp[i] = max(dp[i-1], dp[p] + v)  # skip vs. take current job
17    return dp[n]
18
19# Example usage
20start  = [1, 3, 0, 5, 8, 5]
21finish = [2, 4, 6, 7, 9, 9]
22value  = [5, 6, 5, 4, 11, 2]
23print(f"Maximum total value: {weighted_activity_selection(start, finish, value)}")  # 26