找到最大重叠间隔数的时间段

有一个非常着名的问题。我在这里也是这样问的。
有大象的时间跨度给定，这里的时间跨度是指，出生年份到死亡年份。
你必须计算最大数量的大象活着的时期。找到最大重叠间隔数的时间段

例子：

1990 - 2013 
1995 - 2000 
2010 - 2020 
1992 - 1999 

Answer is 1995 - 1999

我努力解决这个问题，但我不能这样做。

我该如何解决这个问题？

我得到了一种方法，当用户要求查找任何年份的大象数量时。我通过使用分段树来解决这个问题，每当大象给出时间跨度时，每年都会增加1倍。我们可以这样解决这个问题。这可以用来解决上述问题吗？

对于上述问题，我只需要高级方法，我会自己编写代码。

来源

2013-10-03 devsda

你的问题让我困惑。你写*我尝试了很多，但我无法解决这个*然后*我有办法*然后*我只需要的方法，我会自己编码*。这些陈述不一致。你有没有办法？ –

其实我有一个方法，如果用户要求最大数量的大象活着的一年。但不是一段时间。 – devsda

分割每个时间范围为开始日期和结束日期。
排序日期。如果开始日期和结束日期相同，请首先输入结束日期（否则，您可能会获得最佳空日期范围）。
开始通过日期0
迭代的次数使用sweep-line algorithm：
- 如果你得到一个起始日期：
  - 增加计数。
  - 如果当前计数高于最后一次最佳计数，请设置计数，存储此开始日期并设置一个标记。
- 如果你得到一个结束日期：
  - 如果设置了标志，存储存储的开始日期和结束这个日期与计数的最佳间隔为止。
  - 重置标志。
  - 减少计数。

实施例：

对于输入：

1990 - 2013 
1995 - 2000 
2010 - 2020 
1992 - 1999

拆分并分类：（S =开始，E =端）

1990 S, 1992 S, 1995 S, 1999 E, 2000 E, 2010 S, 2013 E, 2020 E

迭代通过他们：在assending为了一年

count = 0 
lastStart = N/A 
1990: count = 1 
     count = 1 > 0, so set flag 
     and lastStart = 1990 

1992: count = 2 
     count = 2 > 0, so set flag 
     and lastStart = 1992 

1995: count = 3 
     count = 3 > 0, so set flag 
     and lastStart = 1995 

1999: flag is set, so 
     record [lastStart (= 1995), 1999] with a count of 3 
     reset flag 
     count = 2 

2000: flag is not set 
     reset flag 
     count = 1 

2010: count = 2 
     since count = 2 < 3, don't set flag 

2013: flag is not set 
     reset flag 
     count = 1 

2020: flag is not set 
     reset flag 
     count = 0

来源

2013-10-03 10:15:11 Dukeling

对于（非常）大量的大象来说，这可能是不值得的。你可以创建一个按年份索引的数组，出生时为+1，死亡时为-1。 O（e）填充，O（n）扫描，其中'e'是大象的数量，'n'是日期范围。 – Geobits

这个怎么样？

说我将上述所有数据存储在一个文件中。将它读入由“ - ”分隔的两个数组中。

因此，现在我有birthYear[]其中包含所有的出生年份和deathYear[]包含所有的死亡年。

所以birthYear [] = [1990，1995，2010，1992 deathYear [] = [2013，2000，2020年，1999年]

获取分钟出生年份和最大的死亡年份。用Key作为一年创建一个哈希表，并将Value作为计数。

因此，

HashTable<String, Integer> numOfElephantsAlive = new HashTable<String, Integer>();

现在，从分钟（BirthYear）到最大（BirthYear），请执行下列操作：通过出生年份阵列

迭代，并做了一个添加到哈希表的所有在BirthYear和相应的DeathYear之间的年份与计数为1.如果密钥已经存在，则为其添加1。因此，对于最后一种情况：

1992 - 1999 
HashTable.put(1992, 1) 
HashTable.put(1993, 1) 
and so on for every year. 

Say, for example, you have a Hashtable that looks like this at the end of it: 

Key Value 
1995  3 
1996  3 
1992  2 
1993  1 
1994  3 
1998  1 
1997  2 
1999  2

现在，您需要大象数量最多的年份范围。因此，让我们迭代并找到具有最大值的年份。这很容易。迭代keySet（）并获得年份。

现在，你需要一个连续的年限。您可以通过两种方式执行此操作：

通过keySet（）执行Collections.sort（），当您达到最大值时，保存所有连续位置。

因此，在1994年我们的例子中选择3，我们会用3来检查所有随后的年份。这会返回您的范围，即年份，最大年度组合。

来源

2013-10-03 09:32:49

我没有理解你的答案。请详细说明。我认为你的例子是错误的。 – devsda

啊..你想要的年份范围。好的...让我更新我的解决方案。 –

一种方法可能是：遍历期间。跟踪到目前为止的时间段列表。注意：在每个步骤中，期数增加2（如果没有与现有期间列表重叠，则为1）。例如

1990 - 2013 
Period List contains 1 period { (1990,2013) } 
Count List contains 1 entry { 1 } 

1995 - 2000 
Period List contains 3 periods { (1990,1995), (1995,2000), (2000,2013) } 
Count List contains 3 entries { 1, 2, 1 } 

2010 - 2020 
Period List contains 5 periods { (1990,1995), (1995,2000), (2000,2010), (2010, 2013), (2013, 2020) } 
Count List contains 5 entries { 1, 2, 1, 2, 1 } 

1992 - 1999 
Period List contains 7 periods { (1990,1992), (1992,1995), (1995,1999), (1999,2000), (2000,2010), (2010, 2013), (2013, 2020) } 
Count List contains 7 entries { 1, 2, 3, 2, 1, 2, 1 }

来源

2013-10-03 10:02:25

1）安排从最大的系列智慧开始。 2）计算整个数据集的最大系列的年数 3）然后确定最大计数。 4）最大的计数是你多年的答案......这可以在Algo中完成。

来源

2015-07-28 12:39:57 himanshu

找到最大重叠间隔数的时间段

回答

相关问题