The Skyline Problem In C++

Introduction:

The Skyline Problem is a classic algorithmic challenge that involves finding the silhouette or "skyline" formed by a series of rectangular buildings on a 2D plane. Imagine a cityscape where each building is represented by a rectangle, defined by its left x-coordinate, height, and right x-coordinate. The goal of the problem is to compute the outline of the city's Skyline as seen from a distance, where only the highest parts of overlapping buildings are visible.

Approach 1: Simple Approach

Implementation:

Example


#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// Structure to represent the key points of the Skyline
struct Point {
    int x, height;
    Point(int x, int height) : x(x), height(height) {}
};
// Comparator for sorting events (building start and end points)
struct Event {
    int x, height;
    bool isStart;
    Event(int x, int height, bool isStart) : x(x), height(height), isStart(isStart) {}
    // Custom comparator to handle the sorting of events
    bool operator<(const Event& e) const {
        if (x != e.x)
            return x < e.x;
        // For tie in x, prioritize the start of a building over the end
        if (isStart && e.isStart)
            return height > e.height; // Higher building comes first
        if (!isStart && !e.isStart)
            return height < e.height; // Lower building ends first
        return isStart; // Start event before end event
    }
};
vector<Point> getSkyline(vector<vector<int>>& buildings) {
    vector<Event> events;
    // Step 1: Convert buildings into events (start and end points)
    for (const auto& building : buildings) {
        int left = building[0];
        int right = building[2];
        int height = building[1];
        events.push_back(Event(left, height, true));   // Building start
        events.push_back(Event(right, height, false)); // Building end
    }
    // Step 2: Sort events based on custom comparator
    sort(events.begin(), events.end());
    // Step 3: Use a max heap to keep track of current building heights
    priority_queue<int> maxHeap;
    maxHeap.push(0); // Initialize with ground level height (0)
    vector<Point> result;
    int prevHeight = 0;
    // Step 4: Process each event
    for (const auto& event : events) {
        if (event.isStart) {
            maxHeap.push(event.height); // Add the building height
        } else {
            // Remove the building height from the heap (need a workaround as we can't remove specific elements from a priority queue)
            vector<int> temp;
            while (!maxHeap.empty() && maxHeap.top() != event.height) {
                temp.push_back(maxHeap.top());
                maxHeap.pop();
            }
            if (!maxHeap.empty()) maxHeap.pop(); // Remove the target height
            for (int h : temp) maxHeap.push(h);  // Restore other heights
        } 
        int currentHeight = maxHeap.top();
        // If the current highest height has changed, record a key point
        if (currentHeight != prevHeight) {
            result.push_back(Point(event.x, currentHeight));
            prevHeight = currentHeight;
        }
    }
    return result;
}
int main() {
    // Sample input: vector of buildings, where each building is defined as [left, height, right]
    vector<vector<int>> buildings = {
        {2, 10, 9}, 
        {3, 15, 7}, 
        {5, 12, 12}, 
        {15, 10, 20},
        {19, 8, 24}
    };
    // Get the Skyline
    vector<Point> skyline = getSkyline(buildings);
    // Print the resulting skyline key points
    cout << "Skyline: ";
    for (const auto& point : skyline) {
        cout << "[" << point.x << ", " << point.height << "] ";
    }
    cout << endl;
    return 0;
}

Output:

Output


Skyline: [2, 10] [3, 15] [7, 12] [12, 0] [15, 10] [20, 8] [24, 0]

Explanation:

Step 1: Representing the Buildings as Events

First, each building is represented by two key points:

✅ A starcpp tutorial where the building begins.
✅ An end point where the building ends.

These points are treated as "events." Each event includes:

✅ The x-coordinate (position on the x-axis).
✅ The height of the building.
✅ Whether the event is a start or end of a building.

Step 2: Sorting the Events

Next, all the events are sorted based on their x-coordinates. This sorting is crucial because it allows us to process the buildings in the correct order from left to right, just as you would view them on a horizon. There are some exceptional cases to handle:

✅ If two events have the same x-coordinate, start events are processed before end events. This is because a new building starting at a particular point could potentially raise the Skyline, which needs to be accounted for before considering any buildings ending at thacpp tutorial.
✅ If two start events share the same x-coordinate, the taller building is processed first, as it has a more significant impact on the Skyline.
✅ Similarly, if two end events share the same x-coordinate, the shorter building is considered first to reflect the transition of heights accurately.

Step 3: Managing Heights with a Max Heap

✅ To keep track of the heights of the buildings currently being considered (i.e., those whose start has been processed but whose end has not yet been reached), a max heap (or priority queue) is used. This data structure efficiently allows us always to know the current maximum height among the active buildings.
✅ When a start event is encountered, the building's height is added to the heap. This height represents a candidate for the Skyline's current maximum height.
✅ When an end event is encountered, it means a building ends at this point. The challenge here is to remove the building's height from the heap. Since directly eliminating elements from a heap isn't straightforward, a workaround involves removing all elements and re-inserting those that are still active (not yet ended) to update the heap.

Step 4: Recording Key Points

After each event is processed, the algorithm checks the current maximum height from the heap:

✅ If this height differs from the previously recorded height, it means there's a change in the Skyline at this x-coordinate. This difference indicates a new key point, which marks a transition in the Skyline's contour.

Step 5: Constructing the Skyline

The result is a sequence of key points that describe the Skyline. Each key point corresponds to an x-coordinate where the height of the skyline changes. By connecting these key points, the full contour of the Skyline can be drawn, representing the highescpp tutorials of all the buildings as viewed from a distance.

Complexity analysis:

Time Complexity

Event Creation:

✅ For each building, two events (start and end) are created.
✅ If there are n buildings, this step involves O(n)

Sorting Events:

✅ The events are sorted based on their x-coordinates, which takes O(n log n) time. Sorting is the most computationally expensive step.

Processing Events:

✅ For each event, the height is either added to or removed from the max heap.
✅ Insertion and removal in a heap both take O(log n) time.
✅ Since there are 2n events, processing all events requires O(2n log n), which simplifies to O(n log n).

Therefore, the overall time complexity is O(n log n), dominated by the sorting step and the heap operations.

Space Complexity

Storing Events:

✅ The algorithm stores 2n events (two per building).
✅ This requires O(2n) space, which simplifies to O(n).

Max Heap:

✅ The heap can contain at most n heights at any point, as all buildings could potentially overlap.
✅ The space required for the heap is O(n).

Result Storage:

✅ The result, which stores the key points of the Skyline, can have at most 2n points in the worst case (when every building adds a new key point).
✅ This requires O(n) space.

Combining these factors, the overall space complexity is O(n).

Approach 2: Using Divide and Conquer Approach

This approach is inspired by the merge sort algorithm and works by recursively breaking down the problem into smaller subproblems, then combining their results to form the final Skyline.

Implementation:

Example


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structure to represent the key points of the Skyline
struct Point {
    int x, height;
    Point(int x, int height) : x(x), height(height) {}
};
// Helper function to merge two skylines
vector<Point> mergeSkylines(const vector<Point>& left, const vector<Point>& right) {
    vector<Point> result;
    int h1 = 0, h2 = 0, currHeight = 0;
    size_t i = 0, j = 0;
    while (i < left.size() || j < right.size()) {
        int x;
        if (i < left.size() && (j >= right.size() || left[i].x < right[j].x)) {
            x = left[i].x;
            h1 = left[i].height;
            ++i;
        } else {
            x = right[j].x;
            h2 = right[j].height;
            ++j;
        }
        int maxHeight = max(h1, h2);
        if (maxHeight != currHeight) {
            result.push_back(Point(x, maxHeight));
            currHeight = maxHeight;
        }
    }
    return result;
}
// Recursive function to divide and conquer
vector<Point> getSkylineRec(const vector<vector<int>>& buildings, int start, int end) {
    if (start > end) {
        return {};
    }
    if (start == end) {
        return {Point(buildings[start][0], buildings[start][1]), Point(buildings[start][2], 0)};
    }
    int mid = (start + end) / 2;
    vector<Point> leftSkyline = getSkylineRec(buildings, start, mid);
    vector<Point> rightSkyline = getSkylineRec(buildings, mid + 1, end);
    return mergeSkylines(leftSkyline, rightSkyline);
}
// Function to prepare input and call the recursive function
vector<Point> getSkyline(vector<vector<int>>& buildings) {
    // Sort buildings by the left edge
    sort(buildings.begin(), buildings.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    return getSkylineRec(buildings, 0, buildings.size() - 1);
}
int main() {
    // Sample input: vector of buildings, where each building is defined as [left, height, right]
    vector<vector<int>> buildings = {
        {2, 10, 9}, 
        {3, 15, 7}, 
        {5, 12, 12}, 
        {15, 10, 20},
        {19, 8, 24}
    };
    // Get the Skyline
    vector<Point> skyline = getSkyline(buildings);
    // Print the resulting skyline key points
    cout << "Skyline: ";
    for (const auto& point : skyline) {
        cout << "[" << point.x << ", " << point.height << "] ";
    }
    cout << endl;
    return 0;
}

Output:

Output


Skyline: [2, 10] [3, 15] [7, 12] [12, 0] [15, 10] [20, 8] [24, 0]

Explanation:

Step1: Sorting the Buildings

Before diving into the divide-and-conquer approach, the buildings are sorted based on their left edge (x-coordinate). This sorting ensures that we process buildings in a left-to-right order, which is crucial for correctly merging the skylines later on.

Step 2: Dividing the Problem

The core idea of divide and conquer is to split the problem into smaller subproblems. Here's how it works:

✅ Base Case: If there is only one building in the current segment, the Skyline for that segment consists of two key points: the start of the building with its height and the end of the building with height zero. This is straightforward as there are no other buildings to consider.
✅ Recursive Division: If there are multiple buildings, the list is divided into two halves. This division continues recursively until each segment contains only one building. The recursive function will handle these smaller segments, eventually breaking down the problem into manageable parts.

Step 3: Conquering the Subproblems

For each segment, the algorithm computes the Skyline . When the segments are reduced to a single building, the Skyline is simply the start and end points of that building. These simple skylines are then used to build up more complex solutions.

Step 4: Merging Skylines

Once the skylines for the left and right halves are computed, they need to be merged to form a continuous skyline for the combined segment. This is done through the following steps:

✅ Initialize Pointers: Use pointers to traverse the skylines from the left and right halves.
✅ Compare Heights: At each x-coordinate, compare the heights from the left and right skylines. Determine the maximum height at that x-coordinate and update the resulting Skyline.
✅ Update Result: If the height changes from the previous x-coordinate, this indicates a new key point in the Skyline. Add this new key point to the result.
✅ Continue Merging: Continue this process until all points from both skylines have been processed.

Step-5: Combining Results

The merging process effectively combines two partial skylines into a single, coherent skyline. By recursively dividing the list of buildings, computing skylines for each segment, and merging these results; the entire Skyline is built up from the smaller pieces.

Complexity analysis:

Time Complexity

Sorting:

✅ Operation: Sorting the buildings by their left edge.
✅ Complexity: O(n log n)
✅ Explanation: This is because sorting requires comparing and ordering each building, where n is the number of buildings.

Recursive Division:

✅ Operation: Recursively dividing the list of buildings into smaller segments until each segment has one building.
✅ Complexity: O(log n) recursive levels.
✅ Explanation: The depth of the recursion tree is logarithmic in the number of buildings.

Merging:

✅ Operation: Merging two skylines.
✅ Complexity: O(n) for each merge.
✅ Explanation: During merging, each segment of buildings is processed linearly to compare and combine the skylines. Since there are approximately log n levels of recursion, and each level processes a total of n elements, merging takes O(n log n) overall.

Total Time Complexity: O(n log n). The most significant factors are sorting and merging du-ring the divide-and-conquer process.

Space Complexity

Storage for Building Events:

✅ Operation: Storing the buildings and their corresponding events.
✅ Complexity: O(n)
✅ Explanation: Each building generates two events (start and end), so the storage required is proportional to the number of buildings.

Recursive Call Stack:

✅ Operation: Space used by the recursion stack during the divide-and-conquer process.
✅ Complexity: O(log n)
✅ Explanation: The depth of the recursion stack is logarithmic in the number of buildings.

Storage for Merged Results:

✅ Operation: Storage of the skyline points resulting from merging.
✅ Complexity: O(n)
✅ Explanation: The resulting skyline points are, at most, linear in the number of buildings.

Total Space Complexity: O(n). The primary space usage comes from storing the building events and the results of merging, with a logarithmic space for the recursion stack.

Introduction:

Approach 1: Simple Approach

Implementation:

Explanation:

Complexity analysis:

Approach 2: Using Divide and Conquer Approach

Implementation:

Explanation:

Complexity analysis:

Input Required