218. The Skyline Problem

public class Solution {
    public IList<IList<int>> GetSkyline(int[][] buildings) {
        var edgeSet = new SortedSet<int>();
        foreach (var building in buildings) {
            edgeSet.Add(building[0]);
            edgeSet.Add(building[1]);
        }
        var edges = edgeSet.ToList();
        var edgeIndexMap = new Dictionary<int, int>();
        for (int i = 0; i < edges.Count; ++i) {
            edgeIndexMap[edges[i]] = i;
        }
        var heights = new int[edges.Count];
        foreach (var building in buildings) {
            int left = building[0], right = building[1], height = building[2];
            int leftIndex = edgeIndexMap[left], rightIndex = edgeIndexMap[right];
            for (int idx = leftIndex; idx < rightIndex; ++idx) {
                heights[idx] = Math.Max(heights[idx], height);
            }
        }
        var answer = new List<IList<int>>();
        for (int i = 0; i < heights.Length; ++i) {
            int currHeight = heights[i], currPos = edges[i];
            if (answer.Count == 0 || answer[answer.Count - 1][1] != currHeight) {
                answer.Add(new List<int> { currPos, currHeight });
            }
        }
        return answer;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<int>> GetSkyline(int[][] buildings) {
        var edgeSet = new SortedSet<int>();
        foreach (var building in buildings) {
            edgeSet.push_back(building[0]);
            edgeSet.push_back(building[1]);
        }
        var edges = edgeSet.ToList();
        var edgeIndexMap = new unordered_map<int, int>();
        for (int i = 0; i < edges.size(); ++i) {
            edgeIndexMap[edges[i]] = i;
        }
        var heights = new int[edges.size()];
        foreach (var building in buildings) {
            int left = building[0], right = building[1], height = building[2];
            int leftIndex = edgeIndexMap[left], rightIndex = edgeIndexMap[right];
            for (int idx = leftIndex; idx < rightIndex; ++idx) {
                heights[idx] = max(heights[idx], height);
            }
        }
        var answer = new List<vector<int>>();
        for (int i = 0; i < heights.size(); ++i) {
            int currHeight = heights[i], currPos = edges[i];
            if (answer.size() == 0 || answer[answer.size() - 1][1] != currHeight) {
                answer.push_back(new List<int> { currPos, currHeight });
            }
        }
        return answer;
    }
}

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        SortedSet<Integer> edgeSet = new TreeSet<Integer>();
        for (int[] building : buildings) {
            int left = building[0], right = building[1];
            edgeSet.add(left);
            edgeSet.add(right);
        }
        List<Integer> edges = new ArrayList<Integer>(edgeSet);
        
        Map<Integer, Integer> edgeIndexMap = new HashMap<>();
        for (int i = 0; i < edges.size(); ++i) {
            edgeIndexMap.put(edges.get(i), i);
        }

        int[] heights = new int[edges.size()];

        for (int[] building : buildings) {
            int left = building[0], right = building[1], height = building[2];
            int leftIndex = edgeIndexMap.get(left), rightIndex = edgeIndexMap.get(right);
            
            for (int idx = leftIndex; idx < rightIndex; ++idx) {
                heights[idx] = Math.max(heights[idx], height);
            }
        }
        
        List<List<Integer>> answer = new ArrayList<>();

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

            if (answer.isEmpty() || answer.get(answer.size() - 1).get(1) != currHeight) {
                answer.add(Arrays.asList(currPos, currHeight));
            }
        }
        return 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;
    }
}

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        positions = sorted(list(set([x for building in buildings for x in building[:2]])))
        
        edge_index_map = {x : i for i, x in enumerate(positions)}

        heights = [0] * len(positions)
        
        for left, right, height in buildings:
            left_idx = edge_index_map[left]
            right_idx = edge_index_map[right]

            for i in range(left_idx, right_idx):
                heights[i] = max(heights[i], height)

        answer = []

        for i in range(len(heights)):
            curr_height = heights[i]
            curr_x = positions[i]

            if not answer or answer[-1][1] != curr_height:
                answer.append([curr_x, curr_height])
        return answer

func getSkyline(buildings [][]int) [][]int {
    edgeSet := make(map[int]struct{})
    for _, building := range buildings {
        edgeSet[building[0]] = struct{}{}
        edgeSet[building[1]] = struct{}{}
    }
    edges := make([]int, 0, len(edgeSet))
    for edge := range edgeSet {
        edges = append(edges, edge)
    }
    sort.Ints(edges)
    edgeIndexMap := make(map[int]int)
    for i, edge := range edges {
        edgeIndexMap[edge] = i
    }
    heights := make([]int, len(edges))
    for _, building := range buildings {
        left, right, height := building[0], building[1], building[2]
        leftIndex, rightIndex := edgeIndexMap[left], edgeIndexMap[right]
        for idx := leftIndex; idx < rightIndex; idx++ {
            if heights[idx] < height {
                heights[idx] = height
            }
        }
    }
    var answer [][]int
    for i, currHeight := range heights {
        currPos := edges[i]
        if len(answer) == 0 || answer[len(answer)-1][1] != currHeight {
            answer = append(answer, []int{currPos, currHeight})
        }
    }
    return answer
}

Algorithm

1️⃣

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

2️⃣

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

3️⃣

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

😎