c++ - 给定不同大象的寿命，找出最大数量的大象生活的时期

Question

我遇到了一个面试问题：

“给定不同大象的寿命。找出最大数量的大象活着的时期。” 例如：
输入：，，[5, 10]输出 ：（3只大象）[6, 15][2, 7]
[6,7]

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

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

如果没有，什么可以很好地解决这个问题？我想用 C++ 编写代码。

任何帮助将不胜感激。

Answer 1

对于每头大象，创建两个事件：大象出生，大象死亡。按日期对事件进行排序。现在浏览事件并计算有多少大象还活着；每次达到新的最大值时，记录开始日期，每次从最大值下降时记录结束日期。

此解决方案不依赖于整数日期。

Answer 2

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

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

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

有可能使用std::map类似map<int,int> （第 1 期，第 2 期 - 大象数量）。它将默认排序。

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

Answer 3

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

确定两个日期范围是否重叠

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

Answer 4

从您的输入中，我发现所有时间段都是重叠的，那么在这种情况下，解决方案很简单

我们被指定为 [start end]

所以答案将是所有开始的最大值和所有结束的最小值。

只需遍历每个时间段并找到所有开始的最大值和所有结束的最小值

注意：当所有时间段都超过一圈时，此解决方案适用

在您的示例中，所有输入的最大值 = 6 所有输出的最小值 = 7

Answer 5

我就做两个阵，一个是大象出生的时候，一个是大象死的时候。对两个数组进行排序。

现在保留一个计数器（最初为零）。开始遍历两个数组并不断从两个数组中获取最小元素。如果我们从 start 数组中获取一个元素，则递增 counter ，否则递减 counter。通过这种方法，我们可以很容易地找到最大值和时间。