我正在嘗試解決以下問題，但我似乎無法弄清楚從哪里開始。如果有人能給我一個有用的見解，將不勝感激！
一群地平的人希望在一塊（顯然）完全平坦的土地上建造一組矩形房屋。當從遠處看房子時，它們形成了一組（重疊的）矩形。扁平地球人希望知道由此產生的 2D 天際線的復雜性。天際線的復雜性是作為矩形聯合邊界一部分的邊數，不考慮地面邊界。構成天際線的矩形以（未排序的）對陣列的形式給出，其中第一個元素是矩形左側的 x 坐標，第二個元素是房子的高度。（換個角度看：你可以說這些是所有矩形的左上角。）例如，房屋 [(15,4),(5,9),(3,5),(7,7),( 1,11),(11,6),(0,8),(13,2)] 對應于復雜度為 16 的天際線：
復雜度為 16 的示例天際線
此外，您對矩形了解以下內容：
- 每個矩形的寬度為 2.5 米，但高度可以在 1 米到 n^2 米之間。
- 最左側矩形的左側的 x 坐標為 0。
- 每個矩形都有不同的 x 坐標，所有 x 坐標都是整數。
- 相鄰房屋之間最多有10米的間隙。
- 沒有兩座房子的高度相同。
描述一種在 O(n) 時間內計算 2D 天際線復雜度的演算法。還要證明你的演算法的正確性并分析它的運行時間。
有誰知道如何解決這個問題的一個很好的起點？
uj5u.com熱心網友回復：
這是一道標準的面試題。通過將每個建筑物視為兩個事件來查看它的最簡單方法：
- 在這一點上
x，一座高樓h開始了。 - 在 點
x 2.5，一座高度的建筑物h結束。
您對這兩個事件進行排序并從左到右掃描它們。您可以跟蹤已經開始但尚未結束的建筑高度。（警告：必須重復高度。使用串列或多重集。）。并且您跟蹤最大高度。當您從左到右掃描此串列時，您可以添加和洗掉建筑物高度的元素。當當前建筑物高度的最大值發生變化時，“當前”高度會發生變化。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/438332.html
上一篇：如何優化解決方案以防止超出記憶體限制錯誤或什么可能讓我出錯？
下一篇：字串向量二分查找