Single segment length of a line I'm trying to get the distance traveled in a collection of routes on a straight line. The rule to determine the distance is that a route segment counts only once. For example given the segments (50, 70) and (60, 80), the total distance covered is 30 instead of 40, because the segment (60, 70) is covered twice.

Sample:

╔═══════╦═══════╦═══════╗
║ Route ║ From  ║  To   ║
╠═══════╬═══════╬═══════╣
║     1 ║   100 ║   110 ║
║     2 ║   115 ║   116 ║
║     3 ║   100 ║   111 ║
║     4 ║     0 ║    15 ║
║     5 ║    50 ║   110 ║
║     6 ║    70 ║   120 ║
╚═══════╩═══════╩═══════╝


In these routes the actual distance traveled was 85m. I made a solution that uses a bit array to control, and a counter to calculate the distance, with this solution the process speed and the memory consumption is good, up to 20250000 meters, after this distance the performance begins to fall. Could they recommend me some algorithm to solve this kind of problem?



Note: These distance are in a straight line, they are not routes that have georeference, they are segments of a straight line.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
public class MainClass {
    static Estacion[] estaciones = new Estacion[]{
          new Estacion(100,110),
          new Estacion(115,116),
          new Estacion(100,111),
          new Estacion(0,15),
          new Estacion(50,110),
          new Estacion(70,120)
      };

  public static void Main (string[] args) {
      Console.WriteLine (Calcular());
  }

  public static int Calcular()
  {

    var min =estaciones.Min(m=&gt; m.Desde);
    var max =estaciones.Max(m=&gt; m.Hasta);

    var recorrido =0;
    var cantidad= max-min;
    var bA = new BitArray(cantidad,false);
    foreach(var e in estaciones.OrderByDescending(o=&gt; o.Longitud))
    {
      var h= ((e.Hasta-e.Desde)/2);
      for(int i= 0;i&lt;= h ; i++)
      {
        var slot=i+e.Desde-min;
        if(slot&lt;cantidad)  
        if(!bA.Get(slot))
        {
           bA.Set(slot,true);
          recorrido++;
        }
        slot=e.Hasta-i-min-1;
        if(!bA.Get(slot)) 
        {
           bA.Set(slot,true);
          recorrido++;
        }
        if(recorrido== cantidad)
          return recorrido;
      }
    }
    return recorrido;
  }

  public class Estacion
  {
    public Guid Id {get; set;}
    public int Desde {get; set;}
    public int Hasta {get; set;}
    public int Longitud {get; set;}

    public Estacion(int a, int b)
    {
      Desde = a;
      Hasta= b;
      Longitud= Hasta-Desde;
      Id= Guid.NewGuid();
    }
  }
}
Algorithm

The time and space complexity of the current algorithm depends on the length of intervals in the input. This is very inefficient for inputs with long intervals, even when there are only few intervals.

The problem can be reworded as: merge the intervals and calculate their total length.
This should be fairly simple to implement efficiently:


Sort the intervals by start position ascending, and end position descending. That is, (5, 10) should come before (5, 8).
Initialize the previous interval = the first, and total = 0
Iterate from the second interval until the end, at each step:


If the current interval is fully included in previous, then skip it
If the current interval overlaps with previous, then update or replace previous to fully include both the previous and the current
If the current interval doesn't overlap with previous, then add the length of previous to total, and replace previous with the current

At the end, add the length of previous to total


Readability

There are serious readability concerns with this code.
This writing style is error-prone and confusing:


var slot=i+e.Desde-min;
if(slot&lt;cantidad)  
if(!bA.Get(slot))
{
   bA.Set(slot,true);
  recorrido++;
}
slot=e.Hasta-i-min-1;



The above should have been written like this:

var slot = i + e.Desde - min;
if (slot &lt; cantidad)
{
    if (!bA.Get(slot))
    {
        bA.Set(slot, true);
        recorrido++;
    }
}
slot = e.Hasta - i - min - 1;


This way the scope of the if statements is perfectly clear.

I also added spaces around operators and after commas as per the convention.

As a side note, in your algorithm the slot &lt; cantidad condition is always true, so in this example the first if statement had no effect,
as if it wasn't even there.