计算不同图层的顶视图

我试图即兴解决问题，在这里给予不同的图层，并且每个图层都在离散范围之间交错颜色，我们必须完全计算这些图层的顶视图。准确地说，它是如何将不同的图层投影到一个图层中的。计算不同图层的顶视图

例如，

到目前为止我有几个见解，

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

计算不同图层的顶视图

回答

相关问题