訪談 - 基於起始和結束值的排序

Question

我在我的一次採訪中得到了這個問題。有一個與開始值和結束值相關的對象數組。與每個對象關聯的計數是其他對象的數量，具有更多的開始時間和更短的結束時間。所以我必須找到與每個對象相關的計數。

我想出了爲O（n^2）解決方案，其中第一我整理的初始值，然後檢查與下一個對象的最終值每個對象的最終值來獲得計數。有沒有更好的算法來解決這個問題。

Answer 1

我沒有找到一個簡單的方法來解決它，也許有點複雜。

我想出了一個解決方案O(nlogn)。像你的解決方案，首先我排序起始值，但在降順序。然後申請一個新的數組a[]保持出現次數的結束值（即，當遇到一個對象（開始，結束），使a[end]加1）。然後遍歷對象陣列，用於對象i與(start, end)，我們只需要添加總和（A [1] | 0 < = I < =端）到最終的答案，然後用a[end] ++更新陣列a，對於sum()查詢，我們可以使用Fenwick tree或Segment tree來計算O(logn)中的每個查詢，因此總複雜度爲O(nlogn)。