3

有一个非常著名的问题。我在这里问同样的问题。
给出了大象时间跨度的数量，这里的时间跨度是指出生年份到死亡年份。
您必须计算最大数量的大象活着的时期。

例子：

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

Answer is   1995 - 1999

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

我怎么解决这个问题？

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

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

4

4 回答 4

9

  • 将每个日期范围拆分为开始日期和结束日期。

  • 对日期进行排序。如果开始日期和结束日期相同，请将结束日期放在第一位（否则您可能会得到一个空的日期范围作为最佳日期）。

  • 从 0 开始计数。

  • 使用扫描线算法遍历日期：

    • 如果您获得开始日期：

      • 增加计数。

      • 如果当前计数高于上一个最佳计数，则设置计数，存储此开始日期并设置标志。

    • 如果您获得结束日期：

      • 如果设置了标志，则存储存储的开始日期和结束日期，并将计数作为迄今为止的最佳间隔。

      • 重置标志。

      • 减少计数。

例子：

对于输入：

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

遍历它们：

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-03T10:15:11.650 回答
0

这个怎么样？

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

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

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

获取最小出生年份和最大死亡年份。创建一个 Hashtable，其中 Key 为年份，Value 为计数。

因此，

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

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

遍历 Birth Year 数组并在 BirthYear 和 Corresponding DeathYear 之间的所有年份中添加 HashTable，计数为 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-03T09:32:49.667 回答
0

一种方法可能是：遍历各个时期。跟踪到目前为止的期间列表。注意：在每一步，周期数增加 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-03T10:02:25.923 回答
0

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

于 2015-07-28T12:39:57.630 回答