В различных задачах программирования часто возникает необходимость объединить перекрывающиеся или соседние интервалы. Этот процесс, известный как «интервалы слияния», является распространенной проблемой во многих областях, таких как планирование, управление временем и анализ данных. В этой статье мы рассмотрим несколько методов решения этой проблемы, приведя примеры кода на Python. Давайте погрузимся!

Метод 1: подход к сортировке
Один простой метод — сортировать интервалы по времени их начала, а затем перебирать их, объединяя соседние или перекрывающиеся интервалы по мере продвижения. Вот пример реализации:

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])  # Sort intervals based on start time
    merged = [intervals[0]]  # Initialize merged list with first interval
    for interval in intervals[1:]:
        if interval[0] <= merged[-1][1]:  # Check for overlap
            merged[-1][1] = max(merged[-1][1], interval[1])  # Merge intervals
        else:
            merged.append(interval)  # Add non-overlapping interval
    return merged

Метод 2: подход на основе стека
Другой подход предполагает использование стека для эффективного объединения интервалов. Мы помещаем интервалы в стек и сравниваем время их начала и окончания. Если интервал пересекается с вершиной стека, мы объединяем их; в противном случае мы помещаем его в стек. Вот пример реализации:

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])  # Sort intervals based on start time
    stack = [intervals[0]]  # Initialize stack with first interval
    for interval in intervals[1:]:
        if interval[0] <= stack[-1][1]:  # Check for overlap
            stack[-1][1] = max(stack[-1][1], interval[1])  # Merge intervals
        else:
            stack.append(interval)  # Add non-overlapping interval
    return stack

Метод 3: деревья интервалов
Для сценариев, в которых операции слияния интервалов выполняются часто, деревья интервалов могут обеспечить эффективные решения. Деревья интервалов — это структуры данных, которые позволяют быстрее искать и объединять интервалы. Хотя реализация деревьев интервалов выходит за рамки этой статьи, стоит отметить их существование как продвинутый метод объединения интервалов.

В этой статье мы рассмотрели три различных метода объединения интервалов: сортировку, на основе стека и деревья интервалов. Первые два метода относительно просты в реализации и обеспечивают эффективные решения для большинства сценариев. С другой стороны, деревья интервалов предлагают расширенные возможности для сценариев, которые включают частые операции слияния интервалов. Поняв эти методы, вы будете хорошо подготовлены к решению проблем слияния интервалов в задачах программирования.