greedy_methods.activity_selection

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

Functions

activity_selection(→ list[tuple[int, int]])

Solve the Activity Selection Problem using a greedy algorithm by selecting

Module Contents

greedy_methods.activity_selection.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