algorithm - 面试 - 根据开始和结束值排序

Question

我在一次面试中遇到了这个问题。有一组对象与起始值和结束值相关联。与每个对象相关联的计数是具有较长开始时间和较短结束时间的其他对象的数量。所以我必须找到与每个对象关联的计数。

我提出了 O(n^2) 解决方案，首先我对起始值进行排序，然后检查每个对象的结束值与下一个对象的结束值以获得计数。有没有更好的算法来解决这个问题。

Answer 1

我没有找到简单的解决方法，可能有点复杂。

我想出了一个O(nlogn) 解决方案。与您的解决方案一样，首先我按起始值排序，但按降序 顺序排列。然后申请一个新数组a[]保持出现次数的结束值(即遇到一个对象时(开始，结束) ，使 a[end] 加一)。然后遍历对象数组，对于(start, end)的对象i，我们只需要添加sum(a[i] | 0<=i<= end) 到最终答案，然后用 a[end]++ 更新数组 a，用于 sum() 查询，我们可以使用Fenwick tree或 Segment tree在 O(logn) 中计算每个查询，因此总复杂度为 O(nlogn)。