arrays - 两个数组，一个有时间，另一个有时间

Question

假设我们有 2 个数组，其中一个(即 A)包含对象 i 进入房间的时间，另一个(即 B)包含时间 i 会离开。这些都没有以任何方式排序，它们的内容都是实数。

例如，对象 3 具有:A[3]=0.785 和 B[3]=4.829。

你如何在 O(nlogn) 中找到在任何给定时间 t 房间中的最大对象？

Answer 1

你可以试试这个:

• 将对象数初始化为零
• 对两个数组进行排序
• 当任一数组中还有剩余元素时
  • 判断哪个数组的第一个值较小
  • 如果“enter”中的第一个值较小，则增加对象的数量并弹出该值
  • 如果“leave”中的第一个值较小，则减少对象的数量并弹出该值
  • 检查您是否找到了新的最大对象数

如果你不能从数组中“弹出”元素，你可以使用两个索引变量来代替；此外，当其中一个数组已经为空时，您还必须添加案例。

排序的复杂度为 O(nlogn)，接下来的循环的复杂度为 O(2*n)，因此总共为 O(nlogn)。