На этом шаге мы рассмотрим общий принцип решения этой задачи.

    Задача очертания заключается в том, чтобы определить контур на фоне неба ряда прямоугольных зданий. Рисунок 1 поясняет задачу.

Рис.1. Задача очертания

    Вход задачи - список из n > 1 прямоугольников, изображающих здания (см. рисунок 1(a)). Нижняя сторона прямоугольников всегда расположена на уровне 0. Таким образом, каждое здание можно определить всего тремя параметрами. В данном случае мы будем использовать кортежи вида (х₁, x₂, h), где х₁ - положение левой стены здания, х₂ - положение его правой стены, а h - его высота, причём х₁ < х₂ и h > 0. Например, [(1, 7, 7), (18, 20, 7), (2, 9, 5), (17, 19, 2), (12, 24, 3), (3, 8, 8), (11, 13, 5), (15, 21, 6)]. Отметим, что нет необходимости сортировать здания каким-либо образом (скажем, по значению х₁).

    Контур, выделенный жирной линией на рисунке 1(b), - это ломаная линия, высота которой в любой точке оси X является высотой максимально высокого здания в этой точке. Так как здания суть прямоугольники, то их контур можно определить набором координат (х, h) на плоскости, которые задают точки х изменения высоты h, как показано на рисунке 1(c). Таким образом, результат задачи - упорядоченный по возрастанию х список пар координат, которые можно представить кортежами. Для приведённого выше примера результатом будет список [(1, 7), (3, 8), (8, 5), (9, 0), (11, 5), (13, 3), (15, 6), (18, 7), (20, 6), (21, 3), (24, 0)].

    Размер задачи - количество зданий n. Начальному условию соответствует наименьший экземпляр задачи - одно здание. Если оно задано кортежем (х₁, x₂, h), то результатом будет список [(x₁, h), (x₂, 0)], как показано на рисунке 2.

Рис.2. Начальное условие задачи очертания для одного здания

    Декомпозицию этой задачи можно осуществить уменьшением её размера на 1. Однако это приводит к алгоритму со временем выполнения в худшем случае Ο(n²). Вместо него мы применим подход "разделяй и властвуй", который позволяет решить задачу за время Ο(n log n). Рисунок 3 иллюстрирует эту идею, которая подобна подходу, применённому в алгоритме сортировки слиянием.

Рис.3. Рекурсивное условие задачи очертания

    Шаг декомпозиции заключается в делении входного списка на два меньших подсписка примерно из n/2 зданий. Тогда метод выполняет два рекурсивных вызова с этими подсписками, которые возвращают два независимых контура. Предположив на основании индукции, что контуры были созданы правильно, последним и главным для получения результата шагом будет объединение контуров. В примере 6.14 приводится отвечающий принципу "разделяй и властвуй" метод, структура которого, в сущности, совпадает с таковой в примере 6.2.

def compute_skyline(buildings):
    n = len(buildings)
    if n == 1:
        return ([(buildings[0][0], buildings[0][2]),
                 (buildings[0][1], 0)])
    else:
        skylines1 = compute_skyline(buildings[0:n // 2])
        skylines2 = compute_skyline(buildings[n // 2:n])
        return merge_skylines(skylines1, skylines2, 0, 0)    

    На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг