缺失日期範圍

Question

我需要從給定日期範圍集合的今年剩餘時間找到所有缺少的日期範圍。所有日期範圍均在同一年內。日期範圍之間沒有重疊。

例如：[（2011年1月31日 - 2011年5月1日），（2011年6月5日 - 2011年12月12日）]可用於收藏 ，那麼缺失的日期範圍是[（1/2011年1月 - 2011年1月30日），（5/2/2011 - 6/4/2011），（12/2/2011-12/31/2011）]

什麼是一種有效的方法解決這個問題？

Answer 1

如果沒有重疊並且所有範圍都是同一年，則可以按開始時間升序排列範圍。然後，缺失的範圍在1月1日到第一個開始日期之間，在所有範圍之間，從最後一個範圍的末尾到12月31日。您需要確保過濾掉可能出現的空白範圍（例如，如果一個範圍一旦下一個範圍開始就結束）。

該算法將花費O（n log n）時間對範圍進行排序，然後用O（n）時間來查找丟失的範圍。或者，如果要實現自己的排序功能，可以使用桶排序或基數排序來排列O（n）時間的範圍，因爲可能的日期範圍很小且有限。第一個版本更容易實現，並在O（n log n）時間內運行，第二個版本在O（n）中運行。

希望這會有所幫助！