Missing Date Ranges

I need to find all the missing date ranges from the rest of the y开发者_如何学运维ear given a collection of date ranges. All the date ranges fall within the same year. And there are no overlaps between the date ranges.

eg: [(1/31/2011 - 5/1/2011), (6/5/2011 - 12/1/2011)] is available in Collection then teh missing date ranges are [(1/1/2011 - 1/30/2011) , (5/2/2011 - 6/4/2011) ,(12/2/2011-12/31/2011)]

What would be an efficient way to solve this problem?

If there are no overlaps and all the ranges are for the same year, you could sort the ranges into ascending order by start time. Then, the missing ranges fall between January 1 and the first start date, between all of the ranges, and from the end of the last range to December 31. You would need to be sure to filter out empty ranges that might arise (for example, if one range ends as soon as the next one starts).

This algorithm would take O(n log n) time to sort the ranges and then O(n) time to find the missing ranges. Alternatively, if you want to implement your own sorting function, you could use a bucket sort or a radix sort to sort the ranges in O(n) time, as the range of possible dates is small and finite. The first version is easier to implement and runs in O(n log n) time, and the second in O(n).

Hope this helps!