problème de division de gamme

Question

les gens,

ont entendu parler de ce problème il ya un certain temps. pensé pour le poster, pour obtenir quelques vues de faire ceci comme utilisant une construction ou d'autres moyens efficaces (arbres spécialisés peuvent être)

Étant donné un ensemble de plages dans les paires (5,18) (12,23) (15,30)

les diviser en toutes les sous-plages possibles qui se chevauchent d'autres plages de l'ensemble. comme (5,11) (12,14) (15,18) (19,23) (24,30)

remercie tous, apprécient que ...

Rajan ...

PS est ce problème aa standard, si oui, tu voudrais connaître son nom

Answer 1

Chuck tous les points d'extrémité de gamme dans une liste, mais les marquer comme début/points d'extrémité.

[(5, S), (18, E), (12, S), (23, E), (15, S), (30, E)] 

Trier les par la position, la rupture des liens en mettant points départ avant la fin des points.

[(5, S), (12, S), (15, S), (18, E), (23, E), (30, E)] 

Ensuite, vous pouvez travailler sur les plages en parcourant cette liste, en gardant la trace du nombre moins des points finaux de démarrage que nous avons examinés jusqu'à présent. Si nous voyons un point de départ, c'est le début d'une nouvelle plage à produire. Si notre compte est positif, nous devons d'abord terminer à la portée actuelle. Si nous voyons un point final, terminez la plage actuelle.

Answer 2

Ok, après un peu de bricolage j'ai été en mesure d'implémenter une version apparemment fonctionnelle. Donc, pour ceux qui sont à la recherche d'une solution de travail, voici le mien:

private static class RangeVal implements Comparable<RangeVal> { 
    public final BigInteger value; 
    public int count; 

    public RangeVal(BigInteger value, int count) { 
     super(); 
     this.value = value; 
     this.count = count; 
    } 

    @Override 
    public String toString() { 
     return value + (isStart() ? "S" : "E") + count; 
    } 

    @Override 
    public int compareTo(RangeVal o) { 
     // Sort by value first 
     int v = value.compareTo(o.value); 
     if (v != 0) 
      return v; 
     // Then sort Starts before ends 
     return -count; 
    } 

    public boolean isStart() { 
     return count > 0; 
    } 

} 

/** 
* Sort a List of ranges by their number, then start/end and merge multiple 
* start/ends 
* 
* @param temp 
*   a list of RangeVal which can be unsorted 
*/ 
private static void preSort(List<RangeVal> temp) { 
    Collections.sort(temp); 
    RangeVal last = null; 
    for (Iterator<RangeVal> iterator = temp.iterator(); iterator.hasNext();) { 
     RangeVal rangeVal = iterator.next(); 
     if ((last != null) && last.value.equals(rangeVal.value) && (last.isStart() == rangeVal.isStart())) { 
      iterator.remove(); 
      last.count += rangeVal.count; 
     } else 
      last = rangeVal; 
    } 
} 

/** 
* Splits a list into ValueRange Objects that do not overlap each other, but 
* fully represent the ranges given by value 
* 
* @param value 
*   a list of RangeVal Objects that need to be split 
* @return 
*/ 
private static SortedSet<ValueRange> split(List<RangeVal> value) { 
    preSort(value); 
    SortedSet<ValueRange> res = new TreeSet<ValueRange>(); 
    int count = 0; 
    BigInteger start = null; 
    for (RangeVal rangeVal : value) { 
     count += rangeVal.count; 
     if (rangeVal.isStart()) { 
      if (start != null) { 
       //If there was an unended start, then we have to end it just one before the new start 
       res.add(new ValueRange(start, rangeVal.value.subtract(BigInteger.ONE))); 
      } 
      //Set the start to the current Element 
      start = rangeVal.value; 
     } else { 
      //End the current range at this Element 
      res.add(new ValueRange(start, rangeVal.value)); 
      if (count > 0) { 
       //If we expect another end later, the element following this will have to start one after 
       start = rangeVal.value.add(BigInteger.ONE); 
      } else 
       //No new range anymore 
       start = null; 
     } 
    } 
    return res; 
} 

public static void main(String[] args) { 
    // 5->8 9->10 11 
    System.out.println(split(createRanges(5, 8, 9, 10, 11, 11))); 
    // 5, 6->7, 8, 9, 10 
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9))); 
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9))); 
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9, 6, 11, 8, 9))); 
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9, 6, 11, 8, 9, 14, 18))); 
} 

private static List<RangeVal> createRanges(int... r) { 
    List<RangeVal> temp = new LinkedList<RangeVal>(); 
    for (int i = 0; i < r.length; i++) { 
     temp.add(new RangeVal(BigInteger.valueOf(r[i]), (i % 2) == 0 ? 1 : -1)); 
    } 
    System.out.println("HDLSimulator.createRanges()" + temp); 
    return temp; 
} 

Answer 3

Peut-être que je manque quelque chose, mais cela semble être une solution simple: rassemble tous les numéros dans un C++ conteneur ensemble STL. Ils seront automatiquement commandés dans l'ordre croissant. donc ils vont lire de cette façon: 5,12,15,18,23,30 Donc, si vous pouvez tolérer le chevauchement alors: (5,12) (12,15) (15,18), (18, 23) (23,30) sont les intervalles qui sont construits en répétant chaque nombre deux fois le premier et le dernier, puis en groupant deux nombres.

Si vous ne pouvez pas tolérer le chevauchement, les plages peuvent être construites en plaçant un nombre incrémenté dans la liste au lieu de le répéter.