Greedy & Dynamic Algorithms

• https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/

Greedy choice property:
This property says that the globally optimal solution can be obtained by making a locally optimal solution (Greedy). The choice made by a Greedy algorithm may depend on earlier choices but not on the future. It iteratively makes one Greedy choice after another and reduces the given problem to a smaller one.

Optimal substructure:
A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the subproblems. That means we can solve subproblems and build up the solutions to solve larger problems.
–https://www.geeksforgeeks.org/greedy-algorithms-general-structure-and-applications/

Example code for activity scheduling:

def greedy_movie_scheduler(movies):
    """
    Select the maximum number of non-overlapping movies.

    Args:
    movies (list of tuples): Each tuple contains two integers (start, finish)
                             representing the start and finish times of a movie.

    Returns:
    list: A list of selected movies in the format (start, finish).
    """
    # Sort movies by their finishing times
    sorted_movies = sorted(movies, key=lambda x: x[1])

    # List to store selected movies
    selected_movies = []

    # The time at which the last selected movie finishes
    last_finish_time = 0

    # Iterate through the sorted list of movies
    for start, finish in sorted_movies:
        # If the movie starts after or when the last selected movie finishes
        if start >= last_finish_time:
            # Select the movie
            selected_movies.append((start, finish))
            # Update the finish time to the finish time of the currently selected movie
            last_finish_time = finish

    return selected_movies

# Example list of movies as (start time, end time)
movies = [(1, 3), (2, 5), (4, 7), (1, 8), (5, 9), (8, 10), (9, 11), (11, 14), (13, 16)]

# Get the list of selected movies
selected_movies = greedy_movie_scheduler(movies)

print("Selected movies:", selected_movies)

Selected movies: [(1, 3), (4, 7), (8, 10), (11, 14)]

---

Proof of Correctness for the Greedy Solution to the Activity Scheduling Problem.

Really, it all comes down to the fact that the solution can be proven via induction to have this property that the finish times of its \(i\)-th element is equal to or before the finish times of the \(i\)-th element of any other candidate solution.

Notation:

• Let \(S\) be the set of activities selected via the greedy algorithm.
• Let \(O\) be any optimal set of activities.
• Activities in \(S\) and \(O\) are both sorted by their finishing times.
• Let \(S = \{ s_1, s_2, ..., s_k \}\) where \(f(s_i) \leq f(s_{i+1})\), where \(f(\cdot)\) represents the finishing time of that element.
• Let \(O = \{ o_1, o_2, ..., o_m \}\) where \(f(o_i) \leq f(o_{i+1})\).

We proceed by induction to show that for any \(i \leq \min (k, m)\), the \(i\)-th activity selected by the greedy algorithm has finish time less than or equal to the finish time of the \(i\)-th finish time in any optimal solution, i.e., \(f(s_i) \leq f(o_i)\).

Base case: For \(i = 1\), the greedy algorithm picks the activity with shortest finishing time, so \(f(s_i) \leq f(o_i)\) by the definition of the greedy choice.

Inductive step: Assume the statement is true for all \(j < i\), and we want to show it for \(i\).

By our inductive hypothesis, \(f(s_{i-1}) \leq f(o_{i-1})\).

The greedy algorithm picks \(s_i\) as the first activity that starts after \(s_{i-1}\) finishes.

Since \(f(s_{i-1}) \leq f(o_{i-1})\), any activity \(o_i\) that is compatible with \(o_{i-1}\) is also compatible with \(s_{i-1}\).

And hence \(f(s_i) \leq f(o_i)\).

Thus by induction, for \(i\) when both \(s_i\) and \(o_i\) exist, \(f(s_i) \leq f(o_i)\).

Therefore the number of activities selected by the greedy algorithm \(k\) is at least as great \(m\), the number found by the optimal solution.

On the other hand, \(m\) is the optimal solution, so it must also be that \(k \leq m\).

Hence \(k = m\).