Filter dates in a date range

Problem
We need to come with a list of dates where our service is online. Considering another list of date range(From through dates) where our service is down for maintenance.
We are looking for a date range of days, months, and may be years. So we might get a huge list of dates.
The 3 blocks on the image below represents down time of a service.

Solution

There are multiple ways to approach this problem but I need a smart way to implement it in O(1) or O(n) in the worst case.

Since I'm using C#. I can use a dictionary of datetime as a key and bool as It's value.

The dictionary keys will be all available dates with default value of true(service is available).

Since It's a dictionary, the insert operation is O(1).

Then we will go through each down time period and update the value of the Date key to true if the date is a key in our dictionary. 

Then we will return a list of Keys where the value is false.

	public class DateRange
	{
	public struct ServiceDownHistory
	{
	public DateTime ServiceDownDate;
	public DateTime ServiceUpDate;
	}
	public List<DateTime> GetServiceOnlineDates(DateTime StartDate, DateTime EndDate, List<ServiceDownHistory> ServiceDownHistoryList)
	{
	Dictionary<DateTime, bool> ServiceAvailabilityFromThrough = new Dictionary<DateTime, bool>();
	DateTime currentDate = StartDate;
	while (currentDate.Date < EndDate)
	{
	if (ServiceAvailabilityFromThrough.ContainsKey(currentDate.Date) == false)
	{
	ServiceAvailabilityFromThrough.Add(currentDate.Date, true);
	}
	currentDate = currentDate.AddDays(1);
	}
	UpdateServiceAvailabilityFromThroughDictionaryByServiceDownHistory(ServiceAvailabilityFromThrough, ServiceDownHistoryList);
	if (ServiceAvailabilityFromThrough.Any(kv => kv.Value == false))
	{
	return ServiceAvailabilityFromThrough.Where(kv => kv.Value == false).Select(kv => kv.Key).ToList<DateTime>();
	}
	return null;
	}
	private void UpdateServiceAvailabilityFromThroughDictionaryByServiceDownHistory
	(Dictionary<DateTime, bool> ServiceAvailabilityFromThrough, IList<ServiceDownHistory> ServiceDownHistoryList)
	{
	foreach (var item in ServiceDownHistoryList)
	{
	var start = item.ServiceDownDate;
	var end = item.ServiceUpDate;
	if (start.Date > DateTime.MinValue)
	{
	DateTime currentDate = start.Date;
	while (currentDate.Date <= end.Date)
	{
	if (ServiceAvailabilityFromThrough.ContainsKey(currentDate.Date) == true)
	{
	ServiceAvailabilityFromThrough[currentDate.Date] = false;
	}
	currentDate = currentDate.AddDays(1);
	}
	}
	}//end of foreach
	}
	}

view raw OnlinseServiceDates hosted with ❤ by GitHub

Results

List of dates where our service is online and functioning.