計算不同圖層的頂視圖

我試圖即興解決問題，在這裏給予不同的圖層，並且每個圖層都在離散範圍之間交錯顏色，我們必須完全計算這些圖層的頂視圖。準確地說，它是如何將不同的圖層投影到一個圖層中的。計算不同圖層的頂視圖

例如，

到目前爲止我有幾個見解，

We need to sort these segments based on ending points (so that I can 
sweep linearly from 0 to 6) 

Split these sorted items into unit intervals. eg. 0-1 (black), 0-1 
(red), 1-2 (red), 2-3 (black), 2-3(green), 3-4 (green), 3-4 (red), 
4-5 (red), 5-6 (black) 

Push each interval into hashmap and update the color for hashmap for 
given interval if it is in a upper layer. 

eg. if we push 0-1 (red) (at layer 0) and we encounter 0-1 (black) 
(at layer 2) we update map with key 0-1 to black. 

Print the map values.

任何想法，從第2步湊合？

來源

2017-08-12 everlasto

你是什麼意思*湊合*？什麼是確切的輸入格式？ – syntagma

輸入格式可以是元組列表（開始，結束，高度，顏色）。通過即興創作，我的意思是任何其他最佳解決方案或改進方法。 – everlasto

此問題是SPOJ就像this問題，它可以通過一個細分受衆羣樹或二進制索引樹得到有效解決，你可以參考this不錯的博客或經過this討論

來源

2017-08-12 16:10:52 marvel308

嘿，我很難理解。因此，分段樹插入需要間隔（l，r），併爲（l，r）的所有子區間構建子樹，並將給定的顏色分配給所有這些節點。接下來我們該做什麼？ – everlasto

因此，現在每個節點只需檢查頂部視圖中哪個顏色描繪了該節點 – marvel308

計算不同圖層的頂視圖

回答

相關問題