{"id":387,"date":"2017-09-22T20:08:33","date_gmt":"2017-09-23T03:08:33","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=387"},"modified":"2018-08-30T14:09:20","modified_gmt":"2018-08-30T21:09:20","slug":"leetcode-218-the-skyline-problem","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-218-the-skyline-problem\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 218. The Skyline Problem"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 218. The Skyline Problem - \u5237\u9898\u627e\u5de5\u4f5c EP68\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/8Kd-Tn_Rz7s?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>A city&#8217;s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are\u00a0<b>given the locations and height of all the buildings<\/b>\u00a0as shown on a cityscape photo (Figure A), write a program to\u00a0<b>output the skyline<\/b>\u00a0formed by these buildings collectively (Figure B).<\/p>\n<p><a href=\"https:\/\/leetcode.com\/static\/images\/problemset\/skyline1.jpg\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"https:\/\/leetcode.com\/static\/images\/problemset\/skyline1.jpg\" alt=\"Buildings\" border=\"0\" \/>\u00a0<\/a><a href=\"https:\/\/leetcode.com\/static\/images\/problemset\/skyline2.jpg\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"https:\/\/leetcode.com\/static\/images\/problemset\/skyline2.jpg\" alt=\"Skyline Contour\" border=\"0\" \/><\/a><\/p>\n<p>The geometric information of each building is represented by a triplet of integers\u00a0<code>[Li, Ri, Hi]<\/code>, where\u00a0<code>Li<\/code>\u00a0and\u00a0<code>Ri<\/code>\u00a0are the x coordinates of the left and right edge of the ith building, respectively, and\u00a0<code>Hi<\/code>\u00a0is its height. It is guaranteed that\u00a0<code>0 \u2264 Li, Ri \u2264 INT_MAX<\/code>,\u00a0<code>0 &lt; Hi \u2264 INT_MAX<\/code>, and\u00a0<code>Ri - Li &gt; 0<\/code>. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.<\/p>\n<p>For instance, the dimensions of all buildings in Figure A are recorded as:\u00a0<code>[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ]\u00a0<\/code>.<\/p>\n<p>The output is a list of &#8220;<b>key points<\/b>&#8221; (red dots in Figure B) in the format of\u00a0<code>[ [x1,y1], [x2, y2], [x3, y3], ... ]<\/code>\u00a0that uniquely defines a skyline.\u00a0<b>A key point is the left endpoint of a horizontal line segment<\/b>. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.<\/p>\n<p>For instance, the skyline in Figure B should be represented as:<code>[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]<\/code>.<\/p>\n<p><b>Notes:<\/b><\/p>\n<ul>\n<li>The number of buildings in any input list is guaranteed to be in the range\u00a0<code>[0, 10000]<\/code>.<\/li>\n<li>The input list is already sorted in ascending order by the left x position\u00a0<code>Li<\/code>.<\/li>\n<li>The output list must be sorted by the x position.<\/li>\n<li>There must be no consecutive horizontal lines of equal height in the output skyline. For instance,\u00a0<code>[...[2 3], [4 5], [7 5], [11 5], [12 7]...]<\/code>\u00a0is not acceptable; the three lines of height 5 should be merged into one in the final output as such:\u00a0<code>[...[2 3], [4 5], [12 7], ...]<\/code><\/li>\n<\/ul>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Sweep line<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-393\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-392\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-391\" style=\"font-size: 1rem;\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-3-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-3-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-390\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-4.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-4-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/218-ep68-4-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><strong>Time Complexity: <\/strong><\/p>\n<p>O(nlogn)<\/p>\n<p><strong>Space Complexity:<\/strong><\/p>\n<p>O(n)<\/p>\n<h1><strong>Solution1: Heap\u00a0<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">class Solution {\r\npublic:\r\n    vector&lt;pair&lt;int, int&gt;&gt; getSkyline(vector&lt;vector&lt;int&gt;&gt;&amp; buildings) {\r\n        \/\/ events,   x,   h,   id,  type (1=entering, -1=leaving)\r\n        vector&lt;Event&gt; events;\r\n        \r\n        int id = 0;\r\n        for (const auto&amp; b : buildings) {\r\n            events.push_back(Event{id, b[0], b[2], 1});\r\n            events.push_back(Event{id, b[1], b[2], -1});\r\n            ++id;\r\n        }\r\n        \r\n        \/\/ Sort events by x\r\n        sort(events.begin(), events.end());\r\n        \r\n        \/\/ Init the heap\r\n        MaxHeap heap(buildings.size());\r\n        \r\n        vector&lt;pair&lt;int, int&gt;&gt; ans;\r\n        \/\/ Process all the events\r\n        for (const auto&amp; event: events) {            \r\n            int x = event.x;\r\n            int h = event.h;\r\n            int id = event.id;\r\n            int type = event.type;            \r\n            \r\n            if (type == 1) {\r\n                if (h &gt; heap.Max()) \r\n                    ans.emplace_back(x, h);\r\n                heap.Add(h, id);\r\n            } else {\r\n                heap.Remove(id);\r\n                if (h &gt; heap.Max())\r\n                    ans.emplace_back(x, heap.Max());\r\n            }            \r\n        }\r\n        \r\n        return ans;\r\n    }\r\nprivate:\r\n    struct Event {\r\n        int id;\r\n        int x;       \r\n        int h;\r\n        int type;\r\n        \r\n        \/\/ sort by x+, type-, h, \r\n        bool operator&lt;(const Event&amp; e) const {\r\n            if (x == e.x)                \r\n                \/\/ Entering event h from large to small\r\n                \/\/ Leaving event h from small to large\r\n                return type * h &gt; e.type * e.h;\r\n            \r\n            return x &lt; e.x;\r\n        }\r\n    };\r\n    \r\n    class MaxHeap {\r\n    public:\r\n        MaxHeap(int max_items): \r\n            idx_(max_items, -1), vals_(max_items), size_(0) {}\r\n        \r\n        \/\/ Add an item into the heap. O(log(n))\r\n        void Add(int key, int id) {\r\n            idx_[id] = size_;\r\n            vals_[size_] = {key, id};\r\n            ++size_;\r\n            HeapifyUp(idx_[id]);\r\n        }\r\n        \r\n        \/\/ Remove an item. O(log(n))\r\n        void Remove(int id) {\r\n            int idx_to_evict = idx_[id];\r\n            \/\/ swap with the last element\r\n            SwapNode(idx_to_evict, size_ - 1);\r\n            --size_;\r\n            HeapifyDown(idx_to_evict);\r\n            HeapifyDown(idx_to_evict);\r\n        }\r\n        \r\n        bool Empty() const {\r\n            return size_ == 0;\r\n        }\r\n        \r\n        \/\/ Return the max of heap\r\n        int Max() const {\r\n            return Empty() ? 0 : vals_.front().first;\r\n        }\r\n    private:\r\n        void SwapNode(int i, int j) {\r\n            if (i == j) return;\r\n            std::swap(idx_[vals_[i].second], idx_[vals_[j].second]);\r\n            std::swap(vals_[i], vals_[j]);\r\n        }\r\n        \r\n        void HeapifyUp(int i) {\r\n            while (i != 0)  {            \r\n                int p = (i - 1) \/ 2;\r\n                if (vals_[i].first &lt;= vals_[p].first) \r\n                    return;\r\n\r\n                SwapNode(i, p);                \r\n                i = p;\r\n            }\r\n        }\r\n        \r\n        \/\/ Make the heap valid again. O(log(n))\r\n        void HeapifyDown(int i) {\r\n            while (true) {\r\n                int c1 = i*2 + 1;\r\n                int c2 = i*2 + 2;\r\n\r\n                \/\/ No child\r\n                if (c1 &gt;= size_) return;\r\n\r\n                \/\/ Get the index of the max child\r\n                int c = (c2 &lt; size_ \r\n                      &amp;&amp; vals_[c2].first &gt; vals_[c1].first ) ? c2 : c1;\r\n\r\n                \/\/ If key[c] is greater than key[i], swap them and\r\n                \/\/ continue to HeapifyDown(c)\r\n                if (vals_[c].first &lt;= vals_[i].first) \r\n                    return;\r\n                \r\n                SwapNode(c, i);\r\n                i = c;\r\n            }\r\n        }\r\n        \r\n        \/\/ {key, id}\r\n        vector&lt;pair&lt;int,int&gt;&gt; vals_;\r\n        \r\n        \/\/ Index of the i-th item in vals_ \r\n        vector&lt;int&gt; idx_;\r\n        \r\n        int size_;\r\n    };\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 91 ms (beats 79.1%)\r\nclass Solution {\r\n    private MaxHeap heap;\r\n    \r\n    public List&lt;int[]&gt; getSkyline(int[][] buildings) {\r\n        int n = buildings.length;        \r\n        \/\/ {x, h, id}\r\n        ArrayList&lt;int[]&gt; es = new ArrayList&lt;int[]&gt;();\r\n        \r\n        for (int i = 0; i &lt; n; ++i) {\r\n            es.add(new int[]{ buildings[i][0], buildings[i][2], i});\r\n            es.add(new int[]{ buildings[i][1], -buildings[i][2], i});\r\n        }\r\n        \r\n        es.sort((e1, e2) -&gt; {\r\n            return e1[0] == e2[0] ? e2[1] - e1[1] : e1[0] - e2[0]; });\r\n        \r\n        \r\n        List&lt;int[]&gt; ans = new ArrayList&lt;int[]&gt;();\r\n        \r\n        heap = new MaxHeap(n);\r\n        \r\n        for (int[] e : es) {\r\n            int x = e[0];\r\n            int h = e[1];\r\n            int id = e[2];\r\n            \r\n            Boolean entering = h &gt; 0;\r\n            h = Math.abs(h);\r\n            \r\n            if (entering) {\r\n                if (h &gt; heap.max())\r\n                    ans.add(new int[]{x, h});\r\n                heap.add(h, id);\r\n            } else {\r\n                heap.remove(id);\r\n                if (h &gt; heap.max())\r\n                    ans.add(new int[]{x, heap.max()});\r\n            }\r\n        }\r\n        \r\n        return ans;\r\n    }\r\n    \r\n    private class MaxHeap {\r\n        \/\/ (key, id)\r\n        private List&lt;int[]&gt; nodes;\r\n        \r\n        \/\/ idx[i] = index of building[i] in nodes\r\n        private int[] idx;\r\n        \r\n        public MaxHeap(int size) {\r\n            idx = new int[size];\r\n            nodes = new ArrayList&lt;int[]&gt;();\r\n        }\r\n        \r\n        public void add(int key, int id) {\r\n            idx[id] = nodes.size();\r\n            nodes.add(new int[]{key, id});\r\n            heapifyUp(idx[id]);\r\n        }\r\n        \r\n        public void remove(int id) {\r\n            int idx_to_evict = idx[id];\r\n            swapNode(idx_to_evict, nodes.size() - 1);\r\n            idx[id] = -1;\r\n            nodes.remove(nodes.size() - 1);\r\n            heapifyUp(idx_to_evict);\r\n            heapifyDown(idx_to_evict);\r\n        }\r\n        \r\n        public Boolean empty() {\r\n            return nodes.isEmpty();\r\n        }\r\n        \r\n        public int max() {\r\n            return empty() ? 0 : nodes.get(0)[0];\r\n        }\r\n        \r\n        private void heapifyUp(int i) {            \r\n            while (i != 0) {            \r\n                int p = (i - 1) \/ 2;\r\n                if (nodes.get(i)[0] &lt;= nodes.get(p)[0])\r\n                    return;\r\n                \r\n                swapNode(i, p);\r\n                i = p;\r\n            }\r\n        }\r\n        \r\n        private void swapNode(int i, int j) {\r\n            int tmpIdx = idx[nodes.get(i)[1]];\r\n            idx[nodes.get(i)[1]] = idx[nodes.get(j)[1]];\r\n            idx[nodes.get(j)[1]] = tmpIdx;\r\n\r\n            int[] tmpNode = nodes.get(i);\r\n            nodes.set(i, nodes.get(j));\r\n            nodes.set(j, tmpNode);\r\n        }\r\n        \r\n        private void heapifyDown(int i) {\r\n            while (true) {\r\n                int c1 = i*2 + 1;\r\n                int c2 = i*2 + 2;\r\n\r\n                if (c1 &gt;= nodes.size()) return;\r\n\r\n                int c = (c2 &lt; nodes.size() \r\n                      &amp;&amp; nodes.get(c2)[0] &gt; nodes.get(c1)[0]) ? c2 : c1;\r\n                \r\n                if (nodes.get(c)[0] &lt;= nodes.get(i)[0])\r\n                    return;\r\n                \r\n                swapNode(c, i);\r\n                i = c;\r\n            }\r\n        }\r\n        \r\n    }\r\n}<\/pre>\n<\/div><\/div>\n<h1>Solution 2: Multiset<\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Time Complexity: O(nlogn)\r\n\/\/ Space Complexity: O(n)\r\n\/\/ Running Time: 22 ms\r\nclass Solution {\r\npublic:\r\n    vector&lt;pair&lt;int, int&gt;&gt; getSkyline(vector&lt;vector&lt;int&gt;&gt;&amp; buildings) {\r\n        typedef pair&lt;int, int&gt; Event; \r\n        \/\/ events,  x,   h\r\n        vector&lt;Event&gt; es;        \r\n        hs_.clear();\r\n        \r\n        for (const auto&amp; b : buildings) {\r\n            es.emplace_back(b[0], b[2]);\r\n            es.emplace_back(b[1], -b[2]);\r\n        }\r\n        \r\n        \/\/ Sort events by x\r\n        sort(es.begin(), es.end(), [](const Event&amp; e1, const Event&amp; e2){\r\n            if (e1.first == e2.first) return e1.second &gt; e2.second;\r\n            return e1.first &lt; e2.first;\r\n        });\r\n        \r\n        vector&lt;pair&lt;int, int&gt;&gt; ans;\r\n        \r\n        \/\/ Process all the events\r\n        for (const auto&amp; e: es) {            \r\n            int x = e.first;\r\n            bool entering = e.second &gt; 0;\r\n            int h = abs(e.second);\r\n            \r\n            if (entering) {                \r\n                if (h &gt; this-&gt;maxHeight()) \r\n                    ans.emplace_back(x, h);\r\n                hs_.insert(h);\r\n            } else {\r\n                hs_.erase(hs_.equal_range(h).first);\r\n                if (h &gt; this-&gt;maxHeight())\r\n                    ans.emplace_back(x, this-&gt;maxHeight());\r\n            }            \r\n        }\r\n        \r\n        return ans;\r\n    }\r\nprivate:\r\n    int maxHeight() const {\r\n        if (hs_.empty()) return 0;\r\n        return *hs_.rbegin();\r\n    }\r\n    multiset&lt;int&gt; hs_;\r\n};<\/pre>\n<\/div><\/div>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: A city&#8217;s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89,70,45],"tags":[217,73,103,104],"class_list":["post-387","post","type-post","status-publish","format-standard","hentry","category-data-structure","category-hashtable","category-tree","tag-hard","tag-heap","tag-skyline","tag-sweep-line","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/387","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=387"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/387\/revisions"}],"predecessor-version":[{"id":3782,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/387\/revisions\/3782"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}