给定不同大象的生命时间，找到大象生活最大数量的时期 [英] Given the life time of different elephants, find the period when maximum number of elephants lived

问题描述

我遇到了一个面试问题：

给定不同大象的生活时间，找到大象最大数量活着的时期。例如：

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

输出： [6,7] / p>

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

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

如果没有，那么什么可以很好地解决这个问题呢？我想在C ++中编码。

任何帮助将不胜感激。

解决方案

对于每个大象，创建两个事件：大象出生，大象死亡。按日期对事件排序。现在走过的事件，只是保持有多少大象活着的计数;每次达到新的最大值时，记录开始日期，并且每次从最大记录结束日期开始。

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

I came across an interview question:

"Given life times of different elephants. Find the period when maximum number of elephants were alive." For example:
Input: [5, 10], [6, 15], [2, 7]
Output: [6,7] (3 elephants)

I wonder if this problem can be related to the Longest substring problem for 'n' number of strings, such that each string represents the continuous range of a time period.

For e.g: [5,10] <=> 5 6 7 8 9 10

If not, what can be a good solution to this problem ? I want to code it in C++.

Any help will be appreciated.

解决方案

For each elephant, create two events: elephant born, elephant died. Sort the events by date. Now walk through the events and just keep a running count of how many elephants are alive; each time you reach a new maximum, record the starting date, and each time you go down from the maximum record the ending date.

This solution doesn't depend on the dates being integers.

这篇关于给定不同大象的生命时间，找到大象生活最大数量的时期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！