Задача: 218. The Skyline Problem
Сложность: hard

Горизонт города — это внешний контур силуэта, образованного всеми зданиями в этом городе, когда они видны издалека. Учитывая расположения и высоты всех зданий, верните горизонт, образованный этими зданиями в совокупности.
Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:
lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.

Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

👨‍💻 Алгоритм:

1️⃣ Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights.

2️⃣ Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex).

3️⃣ Пройдитесь по обновленным высотам и добавьте все позиции, где высота меняется, в answer в качестве ключевых точек горизонта. Верните answer как результат.

😎 Решение:

class Solution {
    getSkyline(buildings) {
        const edgeSet = new Set();
        for (const building of buildings) {
            const [left, right] = building;
            edgeSet.add(left);
            edgeSet.add(right);
        }
        const edges = Array.from(edgeSet).sort((a, b) => a - b);

        const edgeIndexMap = new Map();
        edges.forEach((edge, i) => edgeIndexMap.set(edge, i));

        const heights = new Array(edges.length).fill(0);

        for (const building of buildings) {
            const [left, right, height] = building;
            const leftIndex = edgeIndexMap.get(left);
            const rightIndex = edgeIndexMap.get(right);

            for (let idx = leftIndex; idx < rightIndex; ++idx) {
                heights[idx] = Math.max(heights[idx], height);
            }
        }

        const answer = [];

        for (let i = 0; i < heights.length; ++i) {
            const currHeight = heights[i], currPos = edges[i];

            if (answer.length === 0 || answer[answer.length - 1][1] !== currHeight) {
                answer.push([currPos, currHeight]);
            }
        }
        return answer;
    }
}

Ставь 👍 и забирай 📚 Базу знаний