我遇到了一个面试问题：
“给定不同大象的寿命。找出最大数量的大象活着的时期。” 例如：
输入：，，[5, 10]输出
：（3只大象）[6, 15][2, 7] [6,7]
我想知道这个问题是否与“n”个字符串的最长子字符串问题有关，这样每个字符串都代表一个时间段的连续范围。
例如：
[5,10] <=> 5 6 7 8 9 10
如果没有，什么可以很好地解决这个问题？我想用 C++ 编写代码。
任何帮助将不胜感激。
问问题
928 次
5 回答
8
对于每头大象，创建两个事件：大象出生，大象死亡。按日期对事件进行排序。现在浏览事件并计算有多少大象还活着；每次达到新的最大值时，记录开始日期，每次从最大值下降时记录结束日期。
此解决方案不依赖于整数日期。
于 2012-09-18T19:50:28.467 回答
2
如果我是你在面试中，我会创建一个std::array最大age的大象，然后为每头大象增加元素数量，例如：
[5,10] <<5 to 10从数组中的索引递增所有元素 。
然后我会排序并找到最大的数字在哪里。
有可能使用std::map类似map<int,int> （第 1 期，第 2 期 - 大象数量）。它将默认排序。
我想知道您是否知道更好的解决方案？
于 2012-09-18T19:07:23.480 回答
0
这类似于检查是否缺少括号的程序。它还与日期范围重叠有关。这个主题在 StackOverflow 和其他地方被打死。这里是：
我通过将所有开始/结束范围放在一个结构（或类）向量中然后对它们进行排序来实现这一点。然后你可以遍历向量并检测大象级别的转换。（大象的数量——说明问题的有趣方式！）
于 2012-09-18T19:04:08.957 回答
0
从您的输入中，我发现所有时间段都是重叠的，那么在这种情况下，解决方案很简单
我们被指定为 [start end]
所以答案将是所有开始的最大值和所有结束的最小值。
只需遍历每个时间段并找到所有开始的最大值和所有结束的最小值
注意：当所有时间段都超过一圈时，此解决方案适用
在您的示例中，所有输入的最大值 = 6 所有输出的最小值 = 7
于 2016-09-08T19:23:28.227 回答
0
我就做两个阵，一个是大象出生的时候，一个是大象死的时候。对两个数组进行排序。
现在保留一个计数器（最初为零）。开始遍历两个数组并不断从两个数组中获取最小元素。如果我们从 start 数组中获取一个元素，则递增 counter ，否则递减 counter。通过这种方法，我们可以很容易地找到最大值和时间。
于 2020-08-01T09:01:39.573 回答