Жадные алгоритмы. Задача об интервалах.

Определение

Жадные алгоритмы — это класс алгоритмов, которые делают локально оптимальный выбор в надежде на то, что этот выбор приведет к глобально оптимальному решению задачи. Эти алгоритмы принимают решение на основе текущего состояния проблемы и выбирают лучшее возможное решение в данный момент, не учитывая последствия этого выбора для будущих шагов решения.

Жадные алгоритмы состоят из итераций, решение принимается на каждой итерации, стараясь найти локальное оптимальное решение.

Представьте, что вам нужно посетить нескольких врачей в разных клиниках. Чтобы минимизировать время в пути, вы можете выбрать ближайшую клинику для первого визита, затем выбирать следующую клинику на основе её расположения относительно предыдущей, и так далее. Этот подход кажется логичным на каждом этапе, но он не учитывает общую длину маршрута и может привести к неоптимальному распределению времени.

Задача об интервалах

Задача об интервалах: дано множество отрезков разной длины, необходимо найти максимальную длину множества(кол-во интервалов) в котором отрезки не пересекаются.

1. Отсортируйте отрезки по их конечным точкам.
2. Выберите первый отрезок (с наименьшей конечной точкой).
3. Проходите по списку отрезков и выбирайте каждый следующий отрезок, если он не пересекается с последним выбранным отрезком.

def find_max_non_overlapping_count(intervals):
    start_points = sorted([interval[0] for interval in intervals])
    
    max_count = 0
    current_interval = None
    
    for start in start_points:
        if current_interval is None or start >= current_interval[1]:
            current_interval = (start, intervals[start_points.index(start)][1])
            max_count += 1
            
    return max_count