這是一個面試問題。
以下是按照以下方式排列的註釋，如圖中所示。 給定每個音符的起點和終點。
例如。 [2-5]，[3-9]，[7-100]在長度限制範圍0-10^9 在這個例子中，所有三個音符都將可見。
我們需要找出從頂部查看時有多少個音符可見？
我試圖在O（n * n）中求解，其中n是通過檢查每個音符可見性與每個其他音符的音符數。但在這種方法中，我們將如何確定這兩個音符是否處於不同的音階中。 最終沒有達到解決方案。
O（n）的解決方案將是優選的爲O（n）的溶液通過訪問者要求
如果爲O（n log n）的足夠的：首先，重新映射在輸入的所有數字至0之間..（ 2 * n + 1）（也就是說，如果一個數字x_i是輸入中所有數字中第j個最小的數字，則將所有x_i替換爲j）。然後，您可以在分段樹上使用Painter的算法。
詳細說明：
考慮尺寸的陣列（2 * N + 1）。用-1初始化所有這些單元格。
畫家算法：將鈔票從最後一個（底部）迭代到最頂部。對於從a_i到b_i的每個音符，將索引在a_i和b_i之間的數組中的所有單元格的值替換爲i。在這個算法的最後，我們可以簡單地看看數組中的哪些索引，並且這些索引構成了所有可見的音符。然而，天真地這工作在O（N^2）。
段樹：因此，我們不使用數組，而是使用段樹。上面的操作可以在O（log N）中完成。
如果輸入音符的順序是「前者是在上面」比它的方便：
保持MIN_X和MAX_X的值，它初始化爲第一個音符的x值。遍歷音符，每個x值大於max_x或小於min_x的音符會將這些相應的值更改爲它自己的x值，並被視爲可見，否則不是。完成迭代並返回可見筆記的列表。收集現金。
你怎麼知道哪個範圍在哪個範圍之上？ – 2014-10-06 07:38:53
這正是我在O（n * n）解決方案中遇到的問題 – Guru 2014-10-06 07:40:07
不，我的意思是這裏沒有足夠的信息。頂部還是底部是[3-9]？ – 2014-10-06 07:40:46