Saturday, April 2, 2016

LeetCode OJ - The Skyline Problem

Problem: 

Please find the problem here.

Analysis:

We need to be able to know at all time how high is the tallest building right now, so naturally we would like to do it with a priority queue. We scan from left to right and maintain a priority queue at all time, then we will be able report the result.

Solution:

In order to quickly scan from left to right, we sort the 'events'. An event is when thing changes, so for this problem, it is entering a building and leaving a building. We insert the building's height into a priority queue when we enter and remove it when we are done.

The sorting itself take $ O(n \log n) $ time, each event is processed exactly once and take $ O(\log n) $ time, so the overall complexity is $O(n \log n) $.

There is a couple challenges to the implementation:

1.) Sometimes multiple events happen in the same 'x', so we need to process all events in the same x before we consider to output, and

2.) C++/C# does not come with an implementation of a priority queue, so we have to implement one from scratch.

But it is already my many number of times implementing a priority queue, so it isn't really a big deal. The trick I used is to keep also a backward index from building to heap node index to make removal quick.

The code is almost too long for the judge to accept, I really hate this constraint ...

Code:

#include "stdafx.h"

// https://leetcode.com/problems/the-skyline-problem/

#include "LEET_THE_SKYLINE_PROBLEM.h"
#include <algorithm>
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_THE_SKYLINE_PROBLEM
{
    class Solution
    {
    private:
        class event_comparer
        {
        public:
            event_comparer(vector<vector<int>>& buildings) : m_buildings(buildings) {}
            bool operator() (pair<int, bool> i, pair<int, bool> j)
            {
                int ix = i.second ? this->m_buildings[i.first][0] : this->m_buildings[i.first][1];
                int jx = j.second ? this->m_buildings[j.first][0] : this->m_buildings[j.first][1];
                return ix < jx;
            }
        private:
            vector<vector<int>>& m_buildings;
        };

        class status
        {
        public:
            status(vector<vector<int>>& buildings) : m_buildings(buildings), m_heap_size(0)
            {
                this->m_heap.resize(buildings.size());
                this->m_building_heap_index.resize(buildings.size());
            }

            void insert(int building_index)
            {
                this->m_heap[this->m_heap_size] = building_index;
                this->m_building_heap_index[building_index] = this->m_heap_size;
                this->m_heap_size++;
                this->bubble_up(this->m_heap_size - 1);
            }

            void remove(int building_index)
            {
                int heap_index = this->m_building_heap_index[building_index];
                int last_building = this->m_heap[this->m_heap_size - 1];

                this->m_heap_size--;

                if (building_index == last_building)
                {
                    return;
                }

                this->m_heap[heap_index] = last_building;
                this->m_building_heap_index[last_building] = heap_index;

                if (this->m_heap_size > 0)
                {
                    this->bubble_down(heap_index);
                }
            }

            void bubble_up(int current_index)
            {
                if (current_index == 0)
                {
                    return;
                }

                int parent_index = (current_index + 1) / 2 - 1;
                int current_building = this->m_heap[current_index];
                int parent_building = this->m_heap[parent_index];
                int current_building_height = this->m_buildings[current_building][2];
                int parent_building_height = this->m_buildings[parent_building][2];
                if (current_building_height > parent_building_height)
                {
                    swap(this->m_heap[current_index], this->m_heap[parent_index]);
                    swap(this->m_building_heap_index[current_building], this->m_building_heap_index[parent_building]);
                    this->bubble_up(parent_index);
                }
            }

            void bubble_down(int current_index)
            {
                int right_child_index = (current_index + 1) * 2;
                int left_child_index = right_child_index - 1;

                int current_building = this->m_heap[current_index];
                int current_building_height = this->m_buildings[current_building][2];

                int max_index = current_index;
                int max_building = current_building;
                int max_height = current_building_height;
                if (left_child_index < this->m_heap_size)
                {
                    int left_building = this->m_heap[left_child_index];
                    int left_building_height = this->m_buildings[left_building][2];
                    if (left_building_height > max_height)
                    {
                        max_index = left_child_index;
                        max_building = left_building;
                        max_height = left_building_height;
                    }
                }
                if (right_child_index < this->m_heap_size)
                {
                    int right_building = this->m_heap[right_child_index];
                    int right_building_height = this->m_buildings[right_building][2];
                    if (right_building_height > max_height)
                    {
                        max_index = right_child_index;
                        max_building = right_building;
                        max_height = right_building_height;
                    }
                }
                if (max_index != current_index)
                {
                    swap(this->m_heap[current_index], this->m_heap[max_index]);
                    swap(this->m_building_heap_index[current_building], this->m_building_heap_index[max_building]);
                    this->bubble_down(max_index);
                }
            }

            int height()
            {
                if (this->m_heap_size > 0)
                {
                    int max_building = this->m_heap[0];
                    return this->m_buildings[max_building][2];
                }
                else
                {
                    return 0;
                }
            }

        private:
            vector<vector<int>>& m_buildings;
            int m_heap_size;
            vector<int> m_heap;
            vector<int> m_building_heap_index;
        };

    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings)
        {
            vector<pair<int, int>> result;

            // Step 1: Model each vertical line as an event
            vector<pair<int, bool>> events(buildings.size() * 2); // (building_number, isGoingUp)
            for (size_t i = 0; i < buildings.size(); i++)
            {
                events[i * 2] = pair<int, bool>(i, true);
                events[i * 2 + 1] = pair<int, bool>(i, false);
            }

            // Step 2: Sort the events by x-coordinates
            event_comparer my_event_comparer(buildings);
            sort(events.begin(), events.end(), my_event_comparer);

            // Step 3: Process the event and maintain the status by a heap
            status my_status(buildings);
            int event_index = 0;
            int last_height = 0;
            while (true) // make sure we process all events
            {
                if (event_index == events.size())
                {
                    break;
                }
                bool processed_one_event = false;
                int last_event_x = 1 << 31;

                while (true) // make sure we process all events with the same x
                {
                    if (event_index == events.size())
                    {
                        break;
                    }
                    // Decoding the event
                    pair<int, bool> event = events[event_index];
                    int event_building = event.first;
                    bool event_is_going_up = event.second;
                    int event_x = event_is_going_up ? buildings[event_building][0] : buildings[event_building][1];
                    int event_y = buildings[event_building][2];

                    if (processed_one_event && event_x != last_event_x)
                    {
                        break;
                    }
                    processed_one_event = true;
                    last_event_x = event_x;

                    if (event_is_going_up)
                    {
                        my_status.insert(event_building);
                    }
                    else
                    {
                        my_status.remove(event_building);
                    }

                    event_index++;
                }

                // Did we changed altitude? If so update the skyline
                if (my_status.height() != last_height)
                {
                    result.push_back(pair<int, int>(last_event_x, my_status.height()));
                    last_height = my_status.height();
                }
            }

            return result;
        }
    };
};

using namespace _LEET_THE_SKYLINE_PROBLEM;

int LEET_THE_SKYLINE_PROBLEM()
{
    Solution solution;
    vector<vector<int>> buildings(5);
    buildings[0].push_back(2);  buildings[0].push_back(9);  buildings[0].push_back(10);
    buildings[1].push_back(3);  buildings[1].push_back(7);  buildings[1].push_back(15);
    buildings[2].push_back(5);  buildings[2].push_back(12); buildings[2].push_back(12);
    buildings[3].push_back(15); buildings[3].push_back(20); buildings[3].push_back(10);
    buildings[4].push_back(19); buildings[4].push_back(24); buildings[4].push_back(8);

    vector<pair<int, int>> result = solution.getSkyline(buildings);
    for (size_t i = 0; i < result.size(); i++)
    {
        cout << result[i].first << ", " << result[i].second << endl;
    }

    return 0;
}

No comments :

Post a Comment