Gaps and islands: client solution vs T-SQL query
The following C# code solves the problem:

    var connString =
        "Initial Catalog=MyDb;Data Source=MyServer;Integrated Security=SSPI;Application Name=Benchmarks;";

    var stopWatch = new Stopwatch();
    stopWatch.Start();

    using (var conn = new SqlConnection(connString))
    {
        conn.Open();
        var command = conn.CreateCommand();
        command.CommandText = "dbo.GetAllTaskEvents";
        command.CommandType = CommandType.StoredProcedure;
        var gaps = new List&lt;string&gt;();
        using (var dr = command.ExecuteReader())
        {
            var currentEvents = 0;
            var gapStart = new DateTime();
            var gapStarted = false;
            while (dr.Read())
            {
                var change = dr.GetInt32(1);
                if (change == -1 &amp;&amp; currentEvents == 1)
                {
                    gapStart = dr.GetDateTime(0);
                    gapStarted = true;
                }
                else if (change == 1 &amp;&amp; currentEvents == 0 &amp;&amp; gapStarted)
                {
                    gaps.Add(string.Format("({0},{1})", gapStart, dr.GetDateTime(0)));
                    gapStarted = false;
                }
                currentEvents += change;
            }
        }
        File.WriteAllLines(@"C:\Temp\Gaps.txt", gaps);
    }

    stopWatch.Stop();
    System.Console.WriteLine("Elapsed: " + stopWatch.Elapsed);


This code invokes this stored procedure:

CREATE PROCEDURE dbo.GetAllTaskEvents
AS 
  BEGIN ;
    SELECT  EventTime ,
            Change
    FROM    ( SELECT  StartedAt AS EventTime ,
                      1 AS Change
              FROM    dbo.Tasks
              UNION ALL
              SELECT  FinishedAt AS EventTime ,
                      -1 AS Change
              FROM    dbo.Tasks
            ) AS TaskEvents
    ORDER BY EventTime, Change DESC ;
  END ;
GO


It finds and prints one gap in 2M intervals in the following times, warm cache:

1 gap: Elapsed: 00:00:01.4852029 00:00:01.4444307 00:00:01.4644152


It finds and prints 2M-1 gaps in 2M intervals in the following times, warm cache:

2M-1 gaps Elapsed: 00:00:08.8576637 00:00:08.9123053 00:00:09.0372344 00:00:08.8545477


This is a very simple solution - it took me 10 minutes to develop. A recent college graduate can come up with it. On the database side, execution plan is a trivial merge join which uses very little CPU and memory. 

Edit: to be realistic, I am running client and server on separate boxes.