栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

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

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

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

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

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

  • 从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


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/384007.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号