给定不同大象的寿命，找出大象的最大生存时间。

Question

我遇到了一个面试问题：

“给出不同大象的生命周期。找出大象活着的最大数量。”例如：

输入：[5, 10]、[6, 15]、[2, 7]

输出：[6,7] (3个大象)

我想知道这个问题是否可以与'n‘个字符串的最长子串问题有关，这样每个字符串代表一个时间段的连续范围。

例如：[5,10] <=> 5 6 7 8 9 10

如果不是，有什么可以很好地解决这个问题？我想用C++对它进行编码。

任何帮助都将不胜感激。

Answer 1

为每头大象创建两个事件:大象出生，大象死亡。按日期对事件进行排序。现在浏览这些事件，只需对存活的大象数量进行连续计数；每次达到新的最大值时，记录开始日期，每次从最大值下降时记录结束日期。

这个解决方案不依赖于日期是整数。

Answer 2

如果我是面试中的你，我会用大象的最大age创建一个std::array，然后为每个大象增加元素数量，如下所示：

[5,10] <<递增数组中从索引5 to 10开始的所有元素。

然后我会排序并找出哪里是最大的数字。

有可能使用像map<int,int> (第一阶段，第二数量的大象)这样的std::map。默认情况下将对其进行排序。

我想知道你是否有更好的解决方案？

Answer 3

这类似于检查括号是否丢失的程序。它还与日期范围重叠有关。这个主题在StackOverflow和其他地方被打死了。这就是它：

Determine Whether Two Date Ranges Overlap

我通过将所有的开始/结束范围放在一个结构(或类)的向量中，然后对它们进行排序来实现这一点。然后，您可以遍历向量并检测大象级别的转换。(大象的数量--描述问题的有趣方式！)