时间戳

首页 > 解决方案 > 找出与他人表格最相交的区间的起点和终点

intervals - 找出与他人表格最相交的区间的起点和终点

问题描述

这是一个任务：

夏季花卉展览的策展人正在为活动做准备。他们必须找到一个花开最多的时间。他们有一张包含 (0<n<30) 花及其属性的表格：

ID，开花季节的开始和结束（StartMonth，StartDay，EndMonth，EndDay）

帮助策展人找到展览中花朵最多开花的最早时间（间隔的开始和结束）。

注意：正确的时间不一定是已经存在的时间间隔

由于这是一项任务，我想自己完成大部分工作，我只想就如何从理论上解决这个问题获得建议。

开花季节的样本：

121 6 15 7 25

102 7 1 8 14

236 6 30 8 31

141 7 31 8 10

111 7 1 7 20

128 6 2 6 3

在此处输入图像描述

首先，我将介绍我的方法：

  1. 我做的第一件事是将间隔的月份和日期转换为一个数字格式（例如 MM-DD：08-15 我已更改为 30 + 31 + 15 = 76）
  2. 在那之后，我第一次检查所有的间隔并单独保存一个具有最多交叉点的间隔。
  3. 稍后我再次检查所有间隔，但这次我将它们专门与保存的间隔进行比较，如果它们不与它相交，它们就会被删除，这样我就减少了噪音。
  4. 在这一点上，我认为剩下要做的就是找到与保存的间隔相交的最小间隔。然而，我错了。我没有考虑到最小的间隔可能只有一个交叉点。
  5. 过了一会儿，我意识到我需要找到一个在给定集合中具有最多交叉点并且最小的区间。但我怎样才能找到两者？
  6. 毫无疑问，我的理论还有更多漏洞。我很确定即使我成功了，它仍然会有很多例外。

现在想到它，我脑海中突然冒出一个想法，我可以尝试制作一个 92 天的结构，然后计算哪些天包含最多的开花季节。这很容易，但我不会对这个解决方案感到满意，因为它效率太低了。（轻笑）与我当前一次又一次匹配间隔的代码相比呢？还会低效吗？:D

我也在网上搜索了答案，但只找到了一半。

总而言之，我很想听听其他意见。有什么方法可以妥善处理？我的方法合理还是应该寻找另一种方法？您的帮助将不胜感激。同样，我不是要求一个完整的解决方案，只是轻推答案。提前致谢。

标签： intervalscomputational-geometrytheory

解决方案

通过增加日期对所有区间范围进行排序，将它们加权 +1 表示开始，-1 表示结束。

现在按时间顺序扫描列表，随时添加点权重。每次，这都会给出不同花朵的数量。在你的情况下，012345456 ... 0。

同时，保持迄今为止最高计数的界限（如果是平局，则保持最早的值）。最高间隔的结束只是下一个界限。

如果多个间隔同时开始或结束，则处理首先结束的间隔，以避免零持续时间解决方案。（要实现这一点，只需制作一个比较函数，以便在平局的情况下，-1 具有优先权。）

推荐阅读