Return to Answer

If you don't count the "sorting of the lists" itself, you can iterate through both lists at the same time in a loop (while, not foreach) and only once which would be O(M+N) or even less: O(min(M,N)) (thanks for pointing that out in the comments)

It's too late here for a complete code, but here's a rundown with some pseudocode (comparison methods) to show the algorithm I would use... (EDIT: I'll complete the actual comparisons and update this, since the pseudocode is a bit too pseudo still)

index1 = 0;
index2 = 0;

while (index1 < list1.Count && index2 < list2.Count)
{
         if (list1[index1].overlaps(list2[index2])
         {
              // overlaps - do whatever...
         }

         if (list2[index2].isBefore(list1[index1]))
              index2++;
         else
              index1++;
}

If you don't count the "sorting of the lists" itself, you can iterate through both lists at the same time in a loop (while, not foreach) and only once which would be O(M+N) or even less: O(M+N) is a maximum, for "good sets" it can go as low as O(M) or O(N) depending on overlaps (thanks for pointing that out in the comments)

It's too late here for a complete code, but here's a rundown with some pseudocode (comparison methods) to show the algorithm I would use... (EDIT2: Updated the comparison and validated it against several overlapping scenarios. The "isBefore" was a bit sketchy - "end is before other end" should do the trick)

I still don't think there is a much faster solution... LINQ might make it more "versatile" but certainly not "more efficient" IMHO - with all that method calling in between...

index1 = 0;
index2 = 0; 

// as soon as the first list is exhausted, there can be no more overlaps
while (index1 < list1.Count && index2 < list2.Count)
{
         // check for overlapping timeframe in either direction...
         if (list1[index1].StartTime < list2[index2].EndTime && 
             list1[index1].EndTime > list2[index2].StartTime)
         {
              // overlaps - do whatever...
         }

         // Advance the one list that has the "older" ending time, 
         // doesn't matter whicht if both are equal.
         if (list1[index1].EndTime < list2[index2].EndTime)
              index1++;
         else
              index2++;
}

If you don't count the "sorting of the lists" itself, you can iterate through both lists at the same time in a loop (while, not foreach) and only once which would be O(M+N) or even less: O(min(M,N)) (thanks for pointing that out in the comments)

It's too late here for a complete code, but here's a rundown with some pseudocode (comparison methods) to show the algorithm I would use...

index1 = 0;
index2 = 0;

while (index1 < list1.Count && index2 < list2.Count)
{
         if (list1[index1].overlaps(list2[index2])
         {
              // overlaps - do whatever...
         }
         if (list2[index2].isBefore(list1[index1]))
              index2++;
         else
              index1++;
}

If you don't count the "sorting of the lists" itself, you can iterate through both lists at the same time in a loop (while, not foreach) and only once which would be O(M+N) or even less: O(min(M,N)) (thanks for pointing that out in the comments)

It's too late here for a complete code, but here's a rundown with some pseudocode (comparison methods) to show the algorithm I would use... (EDIT: I'll complete the actual comparisons and update this, since the pseudocode is a bit too pseudo still)

index1 = 0;
index2 = 0;

while (index1 < list1.Count && index2 < list2.Count)
{
         if (list1[index1].overlaps(list2[index2])
         {
              // overlaps - do whatever...
         } 

         if (list2[index2].isBefore(list1[index1]))
              index2++;
         else
              index1++;
}

If you don't count the "sorting of the lists" itself, you can iterate through both lists at the same time in a loop (while, not foreach) and only once which would be O(M+N) or even less O(max(M,N)) if I'm not mistaken.

It's too late here for a complete code, but here's a rundown with some pseudocode (comparison methods) to show the algorithm I would use...

index1 = 0;
index2 = 0;

while (index1 < list1.Count && index2 < list2.Count)
{
         if (list1[index1].overlaps(list2[index2])
         {
              // overlaps - do whatever...
         }
         if (list2[index2].isBefore(list1[index1]))
              index2++;
         else
              index1++;
}

If you don't count the "sorting of the lists" itself, you can iterate through both lists at the same time in a loop (while, not foreach) and only once which would be O(M+N) or even less: O(min(M,N)) (thanks for pointing that out in the comments)

It's too late here for a complete code, but here's a rundown with some pseudocode (comparison methods) to show the algorithm I would use...

index1 = 0;
index2 = 0;

while (index1 < list1.Count && index2 < list2.Count)
{
         if (list1[index1].overlaps(list2[index2])
         {
              // overlaps - do whatever...
         }
         if (list2[index2].isBefore(list1[index1]))
              index2++;
         else
              index1++;
}