Find missing and overlapping numbers in sequences

Question

Let's say we have a data structure like this:

var sequences = new List<Tuple<int, int>>
                {
                    new Tuple<int, int>(1, 10),
                    new Tuple<int, int>(8, 101),
                    new Tuple<int, int>(102, 103),
                    new Tuple<int, int>(104, 104),
                    new Tuple<int, int>(110, 200)
                };

I would like to get two results from this collection:

• All the missing numbers (in this example: 105, 106, 107, 108, 109)
• All the overlapping numbers (in this example: 8, 9, 10)

I could write an algorithm with a couple of loops and helper collections. This off course would work, but I wonder if this could be achieved with the help of LINQ and/or other easier and shorter algorithms?

Edit: My data structure from the example above is representing 5 sequences, the first one containing numbers from 1 to 10, the second one containing the numbers from 8 to 101 and so on... Because in the production the sequences can be much bigger (up to millions), they are not represented with the actual collection (for instance with Lists with all the numbers), but with Tuples, which represents the minimal and the maximal number of each sequence.

Answer 1

You could do it via

var missing = 
      Enumerable.Range(1, 200)
               .Where(i => sequences.All(t => t.Item1 > i || t.Item2 < i));
var overlapping = 
      Enumerable.Range(1, 200)
                .Where(i => sequences.Count(t => t.Item1 <= i && t.Item2 >= i) > 1);

Answer 2

I know algorithm for this problem (it is pseudoCode). ( Complexity classes O(nlog(n)) where n is count of tuple)

So solution is sort Tuple by function:

  int comparer( Tuple a, Tuple b) {
      if ( a.first.compareTo(b.first) == 0 ) {
          return a.second.compareTo(b.second);
      } else 
          return a.first.compareTo(b.first);
  }

so example tuple: (1, 10), (1, 5), (2, 8) will be sort to: (1,5), (1, 10), (2, 8).

Next step is accumulate this result. Iterate on this result and :

 Tuple result = SortedList[0];
 foreach ( Tuple tuple in SortedList ) {

     if ( result.second < tuple.first ) {

        // here you have missing number (result.second, tuple.first)

        result.first = tuple.first; 
        result.second = tuple.second
     } else if ( result.second > tuple.first ) {

        // here you have overlapping number (tuple.first, min( result.second,tuple.second ))

        if ( result.second < tuple.second ) {
              result.second = tuple.second;
        }
     } else {
        result.second = tuple.second;
     }

 }

What we know, that if will be iterate next tuple first number is bigger or equals than result.first. Commentate in code tell you where you have overlapping and missing number