algorithm - 给定一组区间，为什么计算 pred[i] theta(n logn) 的平均情况是？

Question

所以我正在阅读我的笔记，但我并没有真正理解这部分：

定义 f, s 为一个区间的开始和结束时间。按完成时间对所有间隔进行排序。所以假设我们有一组区间 I_1, ..., I_n 并定义 pred[i] = 最大索引 j 使得 f_j <= s_i。（所以基本上在 i 之前的下一个最接近的间隔不与 i 重叠）。

现在我们要为 n 中的所有 I_i 求解所有 pred[i]。为什么这个 theta(n log n) 的运行时间是？我认为，在最坏的情况下，所有 I_1，...，I_(i-1) 都与 I_i 重叠；因此将进行 n - 1 次比较，然后进行 n - 2 次比较，依此类推。最好的情况是没有一个区间重叠，并且 pred(i) 对每个区间进行 1 次比较。我不确定为什么“排序和计算 pred[i] 值”的运行时是 theta(n logn)。

Answer 1

您命名的条件 max j 使得 f[j] < s[i] 不是重叠检查。相反，它是在区间 i 结束之前开始的最后一个区间（它们实际上可能重叠也可能不重叠）。我想你可以得到按开始时间排序的间隔，即 theta(nlogn)，然后使用二进制搜索来为每个 s[i] （也是 theta(nlog n) ）定位 f[j]
由 theta 我的意思是平均情况，不是你提到的最坏的情况。