给定日期范围列表,找到发生最多次数的日期

Question

我有一个Booking包含startDate和的列表endDate.我必须找到预订方面最繁忙的一天.

class Booking {
    Date startDate;
    Date endDate;
}

例:

2016-10-12 to 2016-10-18
2016-10-11 to 2016-10-15
2016-10-13 to 2016-10-14
2016-10-12 to 2016-10-13

从这些日期开始,很明显2016-10-13全部被预订了4次.

我想到的解决方案是:

• 遍历列表中从最小startDate到最大endDate的所有日期
• 记录所有日期的所有预订数量.
• 最后,返回具有最大计数的日期.

但这不是有效的解决方案.我怎样才能有效地找到最忙碌的一天？

Answer 1

1. 为简单起见，为每个日期指定索引（例如最小日期的索引为 0，第二天为 1，依此类推），并初始化用零填充的数组
2. 迭代所有范围，并为开始日期索引递增数组中的元素，并为结束日期递减。（例如，如果某个日期d在范围开始时满足 3 次，在范围结束时满足 5 次，则应该为 -2）
3. 现在，从数组开头迭代所有日期，并将当前元素添加到计数器中（基本上，日期d处的计数器值是它在范围内的频率）
4. 答案是最大计数器值

算法的工作时间为O(n)，其中 n 是minDate和maxDate之间的天数

附言。Patrick Parker 在这篇文章中提到的解决方案也有效，但需要O(m * log(m))时间，其中m是范围数。因此，您应该根据任务规格选择解决方案。