找到的时间段重叠的时间间隔的最大数量 [英] Find the time period with the maximum number of overlapping intervals

问题描述

有一个非常有名的问题。我问了同样在这里。
还有就是给大象时间跨度数，这里的时间跨度指，出生年份死亡年份。
你算算，其中大象的最大数量是活的时间。

There is one very famous problem. I am asking the same here.
There is number of elephants time span given, here time span means, year of birth to year of death.
You have to calculate the period where maximum number of elephants are alive.

示例：

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

Answer is   1995 - 1999

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

I tried hard to solve this, but I am unable to do so.

我该如何解决这个问题呢？

How can I solve this problem?

我当用户请求找到任何一年的大象数量的方法。予解决，通过使用线段树，每当任何大象时间跨度定，每年增加该时间跨度的由1，我们可以解决，以这种方式。可以这样来解决上述问题？

I got approach for when a user asks to find the number of elephants in any year. I solved that by using segment tree, whenever any elephants time span given, increase every year of that time span by 1. We can solve that in this way. Can this be used to solve the above problem?

对于上面的问题，我只需要在高层次的方法，我将code自己来。

推荐答案

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

• Split each date range into start date and end date.

  排序日期。如果开始日期和结束日期都一样，把结束日期第一个（否则你可能会得到一个空的日期范围为最佳）。

  Sort the dates. If a start date and an end date are the same, put the end date first (otherwise you could get an empty date range as the best).

  开始为0的计数。

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

  • 如果你得到一个起始日期：

  • 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.

  复位标志。

  递减计数。

  示例：

  有关输入：

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

  拆分和分类：（取值 =启动，电子 =结束）

  Split and sorted: (S = start, E = end)

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

  迭代通过他们：

  Iterating through them:

  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
  

  这篇关于找到的时间段重叠的时间间隔的最大数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！