查找具有最大重叠间隔数的时间段

查找具有最大重叠间隔数的时间段

• 将每个日期范围划分为开始日期和结束日期。

• 排序日期。如果开始日期和结束日期相同，则将结束日期放在第一位（否则您可能会得到一个空的日期范围作为最佳日期）。

• 从0开始计数。

• 使用扫描线算法遍历日期：

  • 如果您有开始日期：

  • 递增计数。

  • 如果当前计数高于最近的最佳计数，请设置计数，存储此开始日期并设置标志。

  • 如果您获得结束日期：

  • 如果设置了该标志，则将存储的开始日期和此结束日期与计数保存为迄今为止的最佳间隔。

  • 重置标志。

  • 减少计数。

例：

输入：

1990 - 20131995 - 20002010 - 20201992 - 1999

拆分和排序：（

S

=开始，

E

=结束）

1990 S, 1992 S, 1995 S, 1999 E, 2000 E, 2010 S, 2013 E, 2020 E

遍历它们：

count = 0lastStart = N/A1990: count = 1      count = 1 > 0, so set flag        and lastStart = 19901992: count = 2      count = 2 > 0, so set flag        and lastStart = 19921995: count = 3      count = 3 > 0, so set flag        and lastStart = 19951999: flag is set, so        record [lastStart (= 1995), 1999] with a count of 3      reset flag      count = 22000: flag is not set      reset flag      count = 12010: count = 2      since count = 2 < 3, don't set flag2013: flag is not set      reset flag      count = 12020: flag is not set      reset flag      count = 0