The Skyline Problem In C++

Introduction:

The Skyline Challenge is a well-known problem in algorithms that revolves around identifying the outline or "skyline" created by a sequence of rectangular buildings on a two-dimensional plane. Picture a city skyline with each building depicted as a rectangle, characterized by its starting x-coordinate, height, and ending x-coordinate. The objective of this challenge is to calculate the silhouette of the city's skyline, visible from afar, showcasing only the tallest sections of buildings that overlap.

Approach 1: Simple Approach

Implementation:

#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:

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

Explanation:

Step 1: Representing the Buildings as Events

Firstly, every structure is defined by two essential points:

• ✅ The starting point of the building.
• ✅ The terminating point where the building concludes.

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 processing each event, the algorithm verifies the existing peak height from the heap:

Should the current height vary from the previously stored height, it signifies a modification in the Skyline at this specific x-coordinate. This variance highlights a fresh critical juncture that signifies a shift in the Skyline's silhouette.

Step 5: Constructing the Skyline

The outcome consists of a series of essential details outlining the Skyline. Every crucial detail aligns with an x-coordinate indicating a shift in the skyline's height. Connecting these pivotal points allows for the complete outline of the Skyline to be depicted, showcasing the tallest points of all buildings when observed from afar.

Complexity analysis:

Time Complexity

Event Generation:

• ✅ A pair of events (beginning and conclusion) is generated for every structure.
• ✅ In the case of n structures, this process requires O(n) effort.

Arranging Events:

• ✅ Events are organized according to their x-coordinate values, requiring O(n log n) time complexity. The sorting process stands out as the most resource-intensive operation.

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).

Consequently, the total time complexity amounts to O(n log n), where the sorting process and heap operations play a significant role.

Space Complexity

Storing Events:

• ✅ The process involves saving 2n occurrences (two for each structure).
• ✅ This necessitates O(2n) storage capacity, which can be simplified to O(n).

Max Heap:

• ✅ The maximum number of levels in the heap is limited to n, considering the possibility of overlapping buildings.
• ✅ The heap's space complexity is O(n).

Result Storage:

• ✅ The storage of the outcome, containing the essential points of the Skyline, can accommodate a maximum of 2n points under the most adverse scenario (in which each building contributes a new key point).
• ✅ This necessitates O(n) memory allocation.

By combining these elements, the total spatial complexity amounts to O(n).

Approach 2: Using Divide and Conquer Approach

This strategy draws inspiration from the merge sort algorithm and functions by iteratively dividing the task into more manageable subtasks, merging their outcomes to construct the ultimate Skyline.

Implementation:

#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:

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

Explanation:

Step1: Sorting the Buildings

Prior to delving into the divide-and-conquer strategy, the structures are arranged in order of their left boundary (x-coordinate). This arrangement guarantees that we handle structures from left to right, a necessary step for accurately combining the skylines at a later stage.

Step 2: Dividing the Problem

The fundamental concept behind the divide and conquer strategy involves breaking down a complex issue into smaller, more manageable subproblems. Here is an overview of how this technique operates:

• ✅ Base Case: When dealing with a segment containing just a single building, the Skyline for that segment is defined by two crucial points: the building's starting point with its height and the building's endpoint with a height of zero. This process is simple since there are no other buildings to account for.
• ✅ Recursive Division: In scenarios where there are multiple buildings, the list is partitioned into two halves. This partitioning is carried out recursively until each segment comprises only one building. The recursive function is responsible for handling these smaller segments, gradually decomposing the problem into more manageable components.

Step 3: Conquering the Subproblems

For every segment, the algorithm calculates the Skyline. If the segments are condensed into a lone structure, the Skyline consists solely of the initial and final points of that structure. These basic skylines serve as the foundation for constructing more intricate 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 process of merging efficiently merges two incomplete skylines into one unified skyline. Through the iterative subdivision of the building list, calculation of skylines for individual sections, and subsequent integration of these outcomes; the complete Skyline emerges from the fragmented components.

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.

The overall time complexity is O(n log n). Sorting and merging are the key operations during the divide-and-conquer approach, contributing significantly to the total time complexity.

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.

The overall space complexity is O(n). The major space is allocated for saving the events related to buildings and the outcomes of merging, along with a logarithmic space for the stack used in recursion.