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


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

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

Ті періоди, коли команда зайнята, на календарі позначені як діапазони часу, наприклад, з 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)], а на виході Ви повинні отримати впорядкований масив [(0, 1)].

У майбутньому планується внести зміни в програму, де замість 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

Складність алгоритму – 0(n lg n) за часом і 0(n) пам’яттю. 0(n lg n) вийшло через те, що, крім одного проходу по масиву, ми перед цим його сортували.

Джерело: Interview Cake

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *