找到最大重疊間隔數的時間段

有一個非常着名的問題。我在這裏也是這樣問的。
有大象的時間跨度給定，這裏的時間跨度是指，出生年份到死亡年份。
你必須計算最大數量的大象活着的時期。找到最大重疊間隔數的時間段

例子：

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

找到最大重疊間隔數的時間段

回答

相關問題