查找具有最大重叠间隔数的时间段。

Question

有一个非常著名的问题。我也是这么问的。

有多少大象的时间跨度，这里的时间跨度意味着，出生年份到死亡年份。

你必须计算出大象数量最多的时期。

示例：

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

Answer is   1995 - 1999

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

我该如何解决这个问题？

当用户要求在任何一年中找到大象的数量时，我得到了接近。我用分段树解决了这个问题，每当任何大象给定的时间跨度，每年都会增加1，这样我们就可以解决这个问题。这是否可以解决上述问题呢？

对于上面的问题，我只需要高级的方法，我将自己编写它。。

Answer 1

• 将每个日期范围分为开始日期和结束日期。
• 把日期分类。如果开始日期和结束日期相同，将结束日期放在第一位(否则，您可以得到一个空日期范围作为最好的)。
• 从0开始。
• 使用sweep-line algorithm迭代日期

- If you get a start date:

    - Increment the count.
    - If the current count is higher than the last best count, set the count, store this start date and set a flag.

​

- If you get an end date:

    - If the flag is set, store the stored start date and this end date with the count as the best interval so far.
    - Reset the flag.
    - Decrement the count.

​

​

示例：

供投入：

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

拆分和排序：(S = start，E = end)

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

遍历它们：

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

Answer 2

这个怎么样？

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

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

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

得到最小出生年份和最大死亡年份。创建一个哈希表，键作为一年，值作为计数。

因此，

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

现在，从min(BirthYear)到max(BirthYear)，执行以下操作：

迭代出生年份数组，并在HashTable和相应的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()并获得年份。

现在，你需要一个连续的几年。您可以通过两种方式这样做：

在Collections.sort()上执行keySet()，当您到达最大值时，保存所有连续的位置。

因此，当我们的例子在1994年达到3，我们将检查所有以后的年份与一个3，这将返回您的范围，是最小年，最大年组合。

Answer 3

可能有一种方法:遍历周期。记录到现在为止的句号列表。注意:在每个步骤中，周期的数目增加了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 }