找出具有最大重叠区间数量的时间段

Question

找出具有最大重叠区间数量的时间段

4

有一个非常著名的问题，我在这里提出相同的问题。
给定一些象的时间跨度，这里的时间跨度指的是出生年份到死亡年份的时间段。
你需要计算最多象存活的时期。

示例：

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

Answer is   1995 - 1999

我努力解决了这个问题，但是我无法做到。

我该如何解决这个问题？

当用户要查找某一年的大象数量时，我有一个方法。我使用线段树来解决这个问题，每当给出大象时间跨度时，就将该时间跨度的每一年增加1。我们可以用这种方式来解决这个问题。这种方法可以用来解决上述问题吗？

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

- devsda

实际上，如果用户询问最多活着的大象的年份，我有一种方法。但是没有针对时间段的方法。 - devsda

4个回答

0

1）按年份升序排列，从最大系列开始。 2）计算整个数据集中最大系列的年数。 3）然后确定最大计数。 4）最大计数是您的年数答案...这可以通过算法完成。

- himanshu

0

这个怎么样？

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

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

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

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

因此，

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

现在，从最小的出生年份到最大的出生年份，进行以下操作：

遍历出生年份数组，并将 BirthYear 和 Corresponding Death Year 之间的所有年份添加到 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

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

现在，您需要一段连续的年份范围。您可以通过以下两种方式之一完成：

对键集进行Collections.sort()，当达到最大值时，保存所有连续位置。

因此，在我们的示例中，当我们在1994年达到3时，我们将检查随后的所有年份是否为3。这将返回您的范围，即最小年份和最大年份组合。

- gran_profaci

我不明白你的回答，请详细说明。我认为你的例子是错误的。 - devsda

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

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 }

- Abhishek Bansal

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

将每个日期范围拆分为开始日期和结束日期。
对日期进行排序。如果开始日期和结束日期相同，则将结束日期放在前面（否则可能会得到空的日期范围作为最佳结果）。
从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

通过迭代它们：

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