Possible, Question d'Entrevue: Comment Trouver Toutes Chevauchement des Intervalles de

Trier les intervalles point de départ. Puis rabattre sur cette liste, la fusion de chaque intervalle avec son voisin (c'est à dire (1,4),(2,6) -> (1,6)) si elles se chevauchent. La liste contient les intervalles sans superposition de partenaire. Filtre à partir de la liste d'origine.

C'est linéaire dans le temps après la première opération de tri qui peut être fait avec n'importe quel (n log n) de l'algorithme. Pas sûr de savoir comment vous obtenez autour de cela. Même le "filtrer les doublons' opération à la fin est linéaire si vous prenez avantage de déjà-de l'ordre de tri de l'entrée et la sortie de la première opération.

Voici une implémentation en Haskell:

-- Given a list of intervals, select those which overlap with at least one other inteval in the set.
import Data.List

type Interval = (Integer, Integer)

overlap (a1,b1)(a2,b2) | b1 < a2 = False
                       | b2 < a1 = False
                       | otherwise = True

mergeIntervals (a1,b1)(a2,b2) = (min a1 a2, max b1 b2)

sortIntervals::[Interval]->[Interval]
sortIntervals = sortBy (\(a1,b1)(a2,b2)->(compare a1 a2))

sortedDifference::[Interval]->[Interval]->[Interval]
sortedDifference [] _ = []
sortedDifference x [] = x
sortedDifference (x:xs)(y:ys) | x == y = sortedDifference xs ys
                              | x < y  = x:(sortedDifference xs (y:ys))
                              | y < x  = sortedDifference (x:xs) ys

groupIntervals::[Interval]->[Interval]
groupIntervals = foldr couldCombine []
  where couldCombine next [] = [next]
        couldCombine next (x:xs) | overlap next x = (mergeIntervals x next):xs
                                 | otherwise = next:x:xs

findOverlapped::[Interval]->[Interval]
findOverlapped intervals = sortedDifference sorted (groupIntervals sorted)
  where sorted = sortIntervals intervals

sample = [(1,3),(12,14),(2,4),(13,15),(5,10)]

Pas sûr au sujet de O(N) mais que faire si nous avons d'abord les trier par le premier nombre de chaque tuple, et ensuite de façon séquentielle trouver celles dont le premier numéro du tuple est plus grand que le plus grand nombre dans les n-uplets, aussi, qui ne se chevauchent pas avec la prochaine tuple.

De sorte que vous obtenez d'abord:

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

depuis le 4 (la plus grande) < 5 et 10 < 12, {5, 10} est isolé.

Cela impliquerait que nous gardons la trace du plus grand nombre que l'on rencontre, et chaque fois que nous trouvons un tuple dont le nombre de départ est plus grand, nous vérifions si elle se confond avec la suivante.

Cela devient dépendante de l'efficacité de l'algorithme de tri puis, parce que le dernier processus serait O(N)

Si N paires d'intervalles d'entiers, alors nous pouvons l'obtenir en O(n).

Les trier en premier numéro de la paire, puis le deuxième nombre. Si tous sont des entiers, on peut utiliser seau de tri ou tri radix pour l'obtenir en O(n).

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

Puis de combiner un par un,

{1,3}

{1,4} avec chevauchement {1,3} et {2,4}

{1,4}, {5,10}

{1,4}, {5,10}, {12,14}

{1,4}, {5,10}, {12,15} avec chevauchement {12,14} et {13,15}

La combinaison permettrait de prendre en O(N) le temps

Voici un O(N lg N) mise en œuvre en Java qui étend la réponse de @Nikita Rybak.

Ma solution en trouve chaque intervalle qui chevauche au moins un autre intervalle de compte et à la fois comme le chevauchement des intervalles. Par exemple, les deux intervalles (1, 3) et (2, 4) de l'OP question d'origine se chevauchent les uns les autres, et donc dans ce cas il y a 2 chevauchement des intervalles. En d'autres termes, si Un intervalle de chevauchement avec intervalle de B, puis-je ajouter de A et de B pour l'ensemble des intervalles qui se chevauchent.

Maintenant envisager les intervalles de (1, 100), (10, 20) et (30, 50). Mon code constaterez que:

[ 10,  20] overlaps with [  1, 100]
[ 30,  50] overlaps with [  1, 100]

Resulting intervals that overlap with at least one other interval:
[  1, 100]
[ 30,  50]
[ 10,  20]

Afin de prévenir (1, 100) d'être compté deux fois, j'utilise un Java Set qui garde seulement unique Intervalle objets.

Ma solution suivante de ce plan.

1. Sorte que tous les intervalles par un point de départ. Cette étape est O(N lg N).
2. Garder une trace de intervalWithLatestEnd, l'intervalle avec le dernier point de fin.
3. Itérer sur tous les intervalles dans la liste triée. Si un intervalle de chevauchement avec intervalWithLatestEnd, puis ajouter les deux à un Ensemble. Mise à jour intervalWithLatestEnd en cas de besoin. Cette étape est O(N).
4. Retourner le Jeu (et le convertir en une Liste si nécessaire).

Le temps total d'exécution est O(N lg N). Il nécessite un Ensemble de sortie de taille O(N).

Mise en œuvre

Afin d'ajouter d'intervalle pour un jeu, j'ai créé un Intervalle personnalisé de classe qui remplacent equals(), comme prévu.

class Interval {
    int start;
    int end;
    Interval(int s, int e) { 
        start = s; end = e; 
    }

    @Override
    public String toString() {
        return String.format("[%3d, %3d]", start, end);
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + start;
        result = prime * result + end;
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Interval other = (Interval) obj;
        if (start != other.start)
            return false;
        if (end != other.end)
            return false;
        return true;
    }
}

Et voici le code qui s'exécute l'algorithme:

private static List<Interval> findIntervalsThatOverlap(List<Interval> intervals) {

    //Keeps unique intervals.
    Set<Interval> set = new HashSet<Interval>();

    //Sort the intervals by starting time.
    Collections.sort(intervals, (x, y) -> Integer.compare(x.start, y.start));

    //Keep track of the interval that has the latest end time.
    Interval intervalWithLatestEnd = null;

    for (Interval interval : intervals) {

        if (intervalWithLatestEnd != null &&
            interval.start < intervalWithLatestEnd.end) {

            //Overlap occurred.
            //Add the current interval and the interval it overlapped with.
            set.add(interval); 
            set.add(intervalWithLatestEnd);

            System.out.println(interval + " overlaps with " +
                               intervalWithLatestEnd);
        }

        //Update the interval with latest end.
        if (intervalWithLatestEnd == null ||
            intervalWithLatestEnd.end < interval.end) {

            intervalWithLatestEnd = interval;
        }
    }
    //Convert the Set to a List.
    return new ArrayList<Interval>(set);
}

Cas de Test

Ici est un cas de test qui fonctionne le po d'origine intervalles:

public static void testcase() {

    List<Interval> intervals = null;
    List<Interval> result = null;

    intervals = new ArrayList<Interval>();

    intervals.add(new Interval(1, 3));
    intervals.add(new Interval(12, 14));
    intervals.add(new Interval(2, 4));
    intervals.add(new Interval(13, 15));
    intervals.add(new Interval(5, 10));


    result = findIntervalsThatOverlap(intervals);
    System.out.println("Intervals that overlap with at least one other interval:");
    for (Interval interval : result) {
        System.out.println(interval);
    }
}

avec le résultat de:

[  2,   4] overlaps with [  1,   3]
[ 13,  15] overlaps with [ 12,  14]
Intervals that overlap with at least one other interval:
[  2,   4]
[  1,   3]
[ 13,  15]
[ 12,  14]

Enfin, voici une version plus avancée du cas de test:

public static void testcase() {

    List<Interval> intervals = null;
    List<Interval> result = null;

    intervals = new ArrayList<Interval>();

    intervals.add(new Interval(1, 4));
    intervals.add(new Interval(2, 3));
    intervals.add(new Interval(5, 7));
    intervals.add(new Interval(10, 20));
    intervals.add(new Interval(15, 22));
    intervals.add(new Interval(9, 11));
    intervals.add(new Interval(8, 25));
    intervals.add(new Interval(50, 100));
    intervals.add(new Interval(60, 70));
    intervals.add(new Interval(80, 90));


    result = findIntervalsThatOverlap(intervals);
    System.out.println("Intervals that overlap with at least one other interval:");
    for (Interval interval : result) {
        System.out.println(interval);
    }
}

avec le résultat de:

[  2,   3] overlaps with [  1,   4]
[  9,  11] overlaps with [  8,  25]
[ 10,  20] overlaps with [  8,  25]
[ 15,  22] overlaps with [  8,  25]
[ 60,  70] overlaps with [ 50, 100]
[ 80,  90] overlaps with [ 50, 100]
Intervals that overlap with at least one other interval:
[  2,   3]
[  8,  25]
[  9,  11]
[ 50, 100]
[  1,   4]
[ 15,  22]
[ 10,  20]
[ 60,  70]
[ 80,  90]

C'est un simple O(N*log(N)) mise en œuvre en Python:

def overlapping(intervals):
    last = (-1, -1)
    overlapping = set()

    for curr in sorted(intervals, key=lambda p: p[0]):
        if curr[0] < last[1]:
            overlapping.add(curr)
            overlapping.add(last)
        last = max(curr, last, key=lambda p: p[1])

    return list(overlapping - set((-1, -1)))

print overlapping([(1, 3), (12, 14), (2, 4), (13, 15), (5, 10)])
#=> [(1, 3), (13, 15), (2, 4), (12, 14)]

Tout d'abord, il trie les intervalles par la fin du temps, que pour chaque intervalle compare la première fois avec le plus grand temps de mettre fin trouvé, et si elle est plus petite, il signifie qu'il y a un chevauchement.

Le tri de la partie est celui qui nécessite le plus de temps, de sorte que la finale de la complexité est N*log(N).