Задача про слияние промежутков в календаре

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

Те периоды, когда команда занята, на календаре отмечены как диапазоны времени, например, с 10:00 до 12:30 или с 12:30 до 13:00. В разрабатываемой программе промежуток времени представлен в виде кортежей из двух целых чисел. Число означает номер 30-минутного блока, который идет после 9:00 утра. Например, кортеж (2, 4) означает диапазон с 10:00 до 11:00, а (0, 1) — это промежуток 9:00-9:30.

Вам нужно написать функцию, которая должна упростить вывод информации таким образом, что если команда занята в промежутках с 10:00 до 12:30 и с 12:30 до 13:00, то это отображалось как 10:00‒13:00. Например: на входе вашей функции неупорядоченный массив из кортежей [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)], а на выходе вы должны получить упорядоченный массив [(0, 1), (3, 8), (9, 12)].

В будущем планируется внести изменения в программу, где вместо 30-минутных блоков будут минутные, как это реализовано в представлении Unix-времени. С учетом этого изменения нужно, чтобы ваша функция уже сейчас могла работать с большими числами. Еще не забудьте, что кортеж — это такой тип данных, в котором содержимое переменной невозможно изменять после ее создания.

Решение

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

1. Объединять текущий диапазон с предыдущим, сохраняя результат на случай, если потребуется еще одно объединение.
2. Сохраненный результат помещать в выходной массив merged_meetings при условии, что текущий диапазон не объединяется с предыдущим, как и все последующие.

Также необходимо проследить за тем, чтобы последний сохраненный результат попал в выходной массив, так как не будет того же самого условия, как с предыдущими: отсутствие следующего диапазона, который не объединится с текущим.

Код решения на Python:

			def merge_ranges(meetings):

    # сортируем входной массив, помещая его в sorted_meetings.
    sorted_meetings = sorted(meetings)

    # создаем выходной массив, пока что пустой.
    merged_meetings = []

    previous_meeting_start, previous_meeting_end = sorted_meetings[0]

    for current_meeting_start, current_meeting_end in sorted_meetings[1:]:

        # Если текущий диапазон может быть объединен с предыдущим.
        if current_meeting_start <= previous_meeting_end:

            # Сохраняем результат на случай, если
            # текущий диапазон будет расширен еще раз.
            previous_meeting_end = max(current_meeting_end, previous_meeting_end)

        # Если текущий диапазон не может быть объединен с предыдущим.
        else:

            # вставляем результат в выходной массив
            merged_meetings.append((previous_meeting_start, previous_meeting_end))
            previous_meeting_start, previous_meeting_end = \
                current_meeting_start, current_meeting_end

    # вставляем последний результат.
    merged_meetings.append((previous_meeting_start, previous_meeting_end))

    return merged_meetings
		

Сложность алгоритма — O(n lg n) по времени и O(n) по памяти. O(n lg n) получилось из-за того что помимо одного прохода по массиву, мы перед этим его сортировали.