Une gamme algorithme d'intersection de mieux que O(n)?

Gamme intersection est un simple, mais non trivial de problème.

Sa a été répondu deux fois déjà:

La première des solutions est de O(n) et la deuxième solution, c'est une base de données (qui est à moins de O(n), bien sûr).

J'ai le même problème, mais pour un grand n et je ne suis pas dans une base de données.

Ce problème semble être très similaire à Magasin 2D des points pour la récupération rapide de ceux à l'intérieur d'un rectangle mais je ne vois pas comment il peut les cartes.

De sorte que la structure de données voulez-vous de stocker l'ensemble des gammes, tels qu'une recherche sur une gamme coûte moins de O(n)? (Crédit supplémentaire pour l'utilisation de bibliothèques disponibles pour Java)

EDIT:

Je veux obtenir un sous-ensemble de l'ensemble d'intersection des plages, sens de la plage de recherche peuvent se croisent plusieurs plages.

La méthode qui doit être inférieure à O(n) en Java:

public class RangeSet {
    ....
    public Set<Range> intersects(Range range);
    ....
}

Où la Plage est juste une classe contenant une paire de l'int de début et de fin.

Ce n'est pas une question impossible, j'ai déjà la solution, je voulais juste voir si il y avait une plus standard/moyen plus simple de le faire

  • Voulez-vous trouver toutes les plages qui se croisent dans une liste? Ou il suffit de cocher une seule gamme pour les intersections avec une liste de plages?
  • Et avez-vous réellement besoin d'identifier les intersections, ou tout simplement de les détecter? Si vous avez besoin d'identifier toutes les intersections, vous ne pouvez pas battre O(n), comme toutes les plages dans l'ensemble, pourrait se croisent une requête donnée, dans le pire des cas.
  • Comment avez-vous une solution pour ce qui est de moins en moins de O(n) mais peut retourner un ensemble contenant n les plages?
  • Je vais le poster dans le bon temps, si il n'y a pas de meilleure façon
  • Andrew, avec le droit de structures de données, vous n'avez pas à retourner une plage définie, mais les plages de plages de. E. g. dans mon algorithme ci-dessous lorsque vous suppose que vous avez les plages commandé, vous pouvez obtenir l'index de la première et de la dernière plage qui se chevauchent en O(log n) < O(n) (vous n'avez pas explicite dire à chaque jeu)
  • Mais comme vous le dites dans votre réponse, il ne fonctionne que si vous pouvez supposer que vous êtes d'interroger disjoints plages, pas dans le cas général. Je ne suis toujours pas clair à qui la question a été vraiment demander tho.
  • Venez pour penser à elle, ma solution n'est pas moins de O(n), soit...donc je ne vais pas le publier.

InformationsquelleAutor Pyrolistical | 2008-11-19