Algorithme Java pour trouver l'intersection entre les intervalles

tout d'abord, votre structure de données est confuse - si vous essayez de parler d'intervalles de temps discrets, structurez vos données comme cela; par exemple int[][] où le tableau intérieur est toujours de longueur 2, donc votre t1 devient:

int[][] t1 = {{3,6}, {6,9}, {9,10}};

utiliser la bonne structure vous aidera probablement à simplifier votre algorithme et à le rendre plus facile à utiliser.

Mieux que bien structuré, tableaux, cependant, serait d'utiliser un type dédié pour représenter ces intervalles, de sorte que vous pourriez passer autour List<Interval> des objets et faire une sorte de contient vérifier sur eux. Mais ne pas réinventer la roue. Le génial bibliothèque de goyaves fournit unRange classe que vous pouvez utiliser. Même mieux, il fournit également RangeSet et RangeMap des cours qui vous permettent de faire facilement les choses dont vous parlez. Voir aussi leur Fourchettes Expliquées article qui couvre les notions de base.

notez que vous pouvez facilement transformer votre design actuel en Range les objets en interne, si vous ne pouvez pas refonte de la structure du tableau de l'extérieur.

ayant essayé à un moment donné de construire le mien IntervalSet class, laissez-moi vous dire que c'est un problème délicat pour obtenir le droit et vous vous éviterez beaucoup de maux de tête à l'aide de leur bien conçu et très testé la gamme des utilitaires.

Voici la façon dont je ferais ce que vous êtes décrire avec de la goyave-notez que nous évitons même besoin de penser à propos de mathématiques impliqués - Range fait la bonne chose pour nous:

/**
 * Given a Range and an group of other Ranges, identify the set of ranges in
 * the group which overlap with the first range.  Note this returns a Set<Range>
 * not a RangeSet, because we don't want to collapse connected ranges together. 
 */
public static <T extends Comparable<?>> Set<Range<T>>
        getIntersectingRanges(Range<T> intersects, Iterable<Range<T>> ranges) {
    ImmutableSet.Builder<Range<T>> builder = ImmutableSet.builder();
    for(Range<T> r : ranges) {
        if(r.isConnected(intersects) && !r.intersection(intersects).isEmpty()) {
            builder.add(r);
        }
    }
    return builder.build();
}

/**
 * Given a 2-length array representing a closed integer range, and an array of
 * discrete instances (each pair of which therefore represents a closed range)
 * return the set of ranges overlapping the first range.
 * Example: the instances array [1,2,3,4] maps to the ranges [1,2],[2,3],[3,4].
 */
public static Set<Range<Integer>> getIntersectingContinuousRanges(int[] intersects,
        int[] instances) {
    Preconditions.checkArgument(intersects.length == 2);
    Preconditions.checkArgument(instances.length >= 2);
    ImmutableList.Builder<Range<Integer>> builder = ImmutableList.builder();
    for(int i = 0; i < instances.length-1; i++) {
        builder.add(Range.closed(instances[i], instances[i+1]));
    }
    return getIntersectingRanges(Range.closed(intersects[0], intersects[1]),
                                 builder.build());
}

à l'Aide de votre exemples:

public static void main(String[] args)
{
    int[] interval = {5,10};
    int[] t1 = {3,6,9,10};
    int[] t2 = {2,4,5,6,10};

    System.out.println(getIntersectingContinuousRanges(interval, t1));
    System.out.println(getIntersectingContinuousRanges(interval, t2));
}

ci-dessus affiche:

[[3‥6], [6‥9], [9‥10]]
[[4‥5], [5‥6], [6‥10]]