Question d'entretien possible: Comment trouver tous les intervalles se chevauchant

Question

Ce n'est pas une question d'entrevue en soi, que je suis tombé sur ceci dans mon projet, mais j'ai pensé qu'il pourrait être un décent intervew question.

Vous disposez de N paires d'intervalles, dire des entiers. Vous êtes nécessaires pour identifier tous les intervalles qui se chevauchent les uns avec les autres en O(N) fois. Par exemple, si vous avez

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

la réponse est {1, 3}, {12, 14}, {2, 4}, {13, 15}. Notez que vous n'avez pas besoin de leur groupe, de sorte que le résultat peut être dans n'importe quel ordre, comme dans l'exemple.

J'ai juste jeté en O(N) le temps parce que le KMP algorithme prend O(N) pour la chaîne de recherche. :D

Le meilleur, je suis venu avec et ce que je suis en ce moment dans le projet est en O(N^2). Ouais, la force brute est assez triste, mais personne ne se plaint alors je ne vais pas à refactoriser. :P Encore, j'étais curieux de savoir si un plus grand esprit a une solution plus élégante.

Answer 1

Jeter les extrémités des intervalles dans un tableau, en les marquant comme de début ou de fin points. Trier par rompre les liens en plaçant les points d'extrémité avant le démarrage de points si les intervalles sont fermées, ou à l'inverse s'ils sont à moitié ouvertes.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E

Puis itérer sur la liste, garder une trace de combien d'intervalles nous sommes dans (cette valeur correspond au nombre de start-points traités moins nombre de points). Chaque fois que nous avons atteint un point de départ alors que nous sommes déjà dans un intervalle, ce qui signifie que nous devons avoir de chevauchement des intervalles.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
    ^                          ^
   overlap                    overlap

Nous pouvons trouver les intervalles se recoupent avec qui en stockant des données à côté de la fin-points, et de garder trace des intervalles de nous sommes.

C'est un O(N logN) de la solution, avec tri être le principal facteur.

Answer 2

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)]

Answer 3

L'approche standard pour les problèmes d'intervalles en ligne consiste à les trier en fonction du point de départ, puis à marcher du premier au dernier. O(n*logn) ( O(n) si déjà trié)

 end = 0;
for (current in intervals) {
    if current.start < end {
        // there's an intersection!
        // 'current' intersects with some interval before it
        ...
    }
    end = max(end, current.end)
}
 

Answer 4

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.

Donc, vous devez tout d'abord obtenir:

{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)

Answer 5

Supposons que la différence entre le départ et les points de terminaison est petit, dire < 32. par exemple. 1..32. Puis chaque intervalle peut être écrite comme une séquence de bits en 32 bits mot. e.g [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110. Deux intervalles, ou des combinaisons d'intervalles, se chevauchent si leur niveau du bit AND est non-nul. par exemple. [1,2] chevauche [1,3] car 001&011 == 001, non-zéro. O(n) alg est pour garder un bit à bit OU d'intervalles vu jusqu'à présent et AND chaque nouveau:

bitsSoFar = 0
for (n=0; n < bitPatterns.length; n++)
    if (bitPatterns[n] & bitsSoFar != 0)
        // overlap of bitPatterns[n] with an earlier pattern
        bitsSoFar |= bitPatterns[n]

À gauche comme un exercice:

• modifier l'algorithme afin d'identifier le chevauchement d'une séquence de bits avec une version ultérieure

• travailler sur le motif de bits pour un intervalle de temps en O(1)