mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 21:45:27 +08:00
2c3bcdda4e
* Add activity selection new algorithm * updating DIRECTORY.md * Rename x to activity * updating DIRECTORY.md * updating DIRECTORY.md * Refactor activity_selection function documentation Updated docstring and added a check for empty input. * Fix activity_selection function test cases --------- Co-authored-by: Hardvan <Hardvan@users.noreply.github.com> Co-authored-by: Christian Clauss <cclauss@me.com> Co-authored-by: cclauss <cclauss@users.noreply.github.com>
58 lines
2.0 KiB
Python
58 lines
2.0 KiB
Python
"""
|
|
The Activity Selection Problem is a classic problem in which a set of activities,
|
|
each with a start and end time, needs to be scheduled in such a way that the
|
|
maximum number of non-overlapping activities is selected.
|
|
This is a greedy algorithm where at each step,
|
|
we choose the activity that finishes the earliest
|
|
and does not conflict with previously selected activities.
|
|
|
|
Wikipedia: https://en.wikipedia.org/wiki/Activity_selection_problem
|
|
"""
|
|
|
|
|
|
def activity_selection(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
|
|
"""
|
|
Solve the Activity Selection Problem using a greedy algorithm by selecting
|
|
the maximum number of non-overlapping activities from a list of activities.
|
|
|
|
Parameters:
|
|
activities: A list of tuples where each tuple contains
|
|
the start and end times of an activity.
|
|
|
|
Returns:
|
|
A list of selected activities that are non-overlapping.
|
|
|
|
Example:
|
|
>>> activity_selection([(1, 3), (2, 5), (3, 9), (6, 8)])
|
|
[(1, 3), (6, 8)]
|
|
|
|
>>> activity_selection([(0, 6), (1, 4), (3, 5), (5, 7), (5, 9), (8, 9)])
|
|
[(1, 4), (5, 7), (8, 9)]
|
|
|
|
>>> activity_selection([(1, 2), (2, 4), (3, 5), (0, 6)])
|
|
[(1, 2), (2, 4)]
|
|
|
|
>>> activity_selection([(5, 9), (1, 2), (3, 4), (0, 6)])
|
|
[(1, 2), (3, 4), (5, 9)]
|
|
|
|
>>> all(activity_selection(x) == [] for x in ([], {}, None, False, 0, 0.0))
|
|
True
|
|
"""
|
|
if not activities:
|
|
return []
|
|
|
|
# Step 1: Sort the activities by their end time
|
|
sorted_activities = sorted(activities, key=lambda activity: activity[1])
|
|
|
|
# Step 2: Select the first activity (the one that finishes the earliest)
|
|
# as the initial activity
|
|
selected_activities = [sorted_activities[0]]
|
|
|
|
# Step 3: Iterate through the sorted activities and select the ones
|
|
# that do not overlap with the last selected activity
|
|
for i in range(1, len(sorted_activities)):
|
|
if sorted_activities[i][0] >= selected_activities[-1][1]:
|
|
selected_activities.append(sorted_activities[i])
|
|
|
|
return selected_activities
|