Unique length of segments of a line

Question

Unique length of segments of a line

Navigation

#1 by (1 votes)

1

I am trying to get the distance traveled in a collection of straight line trips. The rule to determine the distance is that only the only sections count, if it happens more than once only the first counts. Example:

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

In these tours the only distance was 85m. Make a solution that uses a bit array for control, and a counter to calculate the distance, this speed and memory consumption up to 20250000 meters is good, the performance declines. Could you recommend me some algorithm to solve this type of problem?

Update, another example of a similar problem

A similar problem is for the union of different set of number numbers, of which we only have the beginning and the end for each set, we want to know the number of numbers resulting from the union of these:

The set P are number from exclusive 0 to 15, the set Q is from numbers from exclusive 11 to 15, and the set R is from exclusive 14 to 20, the union of these sets gives a new group of 20 unique elements.

Note that these distances are in a straight line, they are not routes that have a georeference, but 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=> m.Desde);
    var max =estaciones.Max(m=> m.Hasta);

    var recorrido =0;
    var cantidad= max-min;
    var bA = new BitArray(cantidad,false);
    foreach(var e in estaciones.OrderByDescending(o=> o.Longitud))
    {
      var h= ((e.Hasta-e.Desde)/2);
      for(int i= 0;i<= h ; i++)
      {
        var slot=i+e.Desde-min;
        if(slot<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();
    }
  }
}

c# algoritmos

asked by Byron 22.04.2017 в 07:02

source

1 answer

ImportError: No module named urls, Creating view in django Get "variables" in Swi Prolog

score 1 · Accepted Answer

Post this question also on Code Review and kindly the community I gave myself an answer

Sort the intervals by the start position ascending, and by the position where it ends in descending order.

Start the previous interval with the first interval and the total in 0.

Iterate from the second element to the last and every iteration:

If the current interval is contained in the previous one, ignore this one.

If the current interval overlaps with the previous one, update or replace the previous interval to fully include both.

If the previous interval does not overlap with the previous one, add the size of the current interval to the total and replace the previous interval with the previous one.

This would be the implementation of those instructions

using System;
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), new Estacion(0, 20250000) };
    public static void Main(string[] args)
    {
        Console.WriteLine(Calcular());
    }

    public static int Calcular()
    {
        var min = estaciones.Min(m => m.Desde);
        var max = estaciones.Max(m => m.Hasta);
        var total = 0;        
        Estacion estacionActual = null;
        foreach (var item in estaciones.OrderBy(o => o.Desde).ThenByDescending(o => o.Hasta))
        {
            Console.WriteLine(item.ToString());
            if (estacionActual == null)
            {
                estacionActual = item;
                total = item.Longitud;
            }
            else
            {
                if ((estacionActual.Desde <= item.Desde) && (item.Desde <= estacionActual.Hasta) && (estacionActual.Hasta < item.Hasta))
                {
                    total += item.Hasta - estacionActual.Hasta;
                    estacionActual.Hasta = item.Hasta;
                    continue;
                }
                else
                {
                    if ((estacionActual.Desde < item.Desde) && (estacionActual.Hasta < item.Desde))
                    {
                        total += item.Hasta - item.Desde;
                        estacionActual = item;
                    }
                }
            }
        }

        return total;
    }

    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();
        }

        public override string ToString()
        {
            return String.Format("{0},{1}", Desde, Hasta);
        }
    }
}