Trouver l'index de l'intervalle non chevauchant le plus proche à droite de chacun des N intervalles donnés

Une représentation d'intervalle standard comprend généralement un ensemble de points de début et de fin appariés. Trouver l'intervalle non chevauchant le plus proche à droite de chaque intervalle spécifié constitue notre dilemme actuel. Cette tâche est d'une importance capitale dans de nombreuses applications différentes, telles que l'allocation de ressources et la planification, car elle implique l'identification de l'intervalle suivant qui ne coupe pas ou ne contient pas l'intervalle actuel.

Grammaire

Pour vous aider à comprendre la démonstration de code que nous sommes sur le point de montrer, examinons d'abord la syntaxe que nous utiliserons avant de plonger dans l'algorithme.

// Define the Interval structure
struct Interval {
   int start;
   int end;
};

// Function to find the index of closest non-overlapping interval
vector<int> findClosestNonOverlappingInterval(const vector<interval>& intervals) {
   // Implementation goes here
}
</interval></int>

Algorithme

Résoudre ce problème nécessite une approche organisée centrée sur l'itération des intervalles dans l'ordre inverse tout en conservant une pile d'index pointant vers leurs partenaires non chevauchants les plus proches. Voici les étapes brèves mais efficaces de la façon dont notre algorithme proposé résout ce problème -

• Créez une pile vide pour stocker les indices des plages qui ne se chevauchent pas.

• Initialisez un vecteur d'index avec une taille égale au nombre d'intervalles, complété par -1 pour indiquer qu'un intervalle non chevauchant n'a pas été trouvé.

• Parcourez les intervalles de droite à gauche.

• Si la pile n'est pas vide et qu'il y a une zone transversale entre l'intervalle actuel et l'intervalle supérieur, procédez à l'élimination (pop) de cet index le plus haut de ladite pile.

• Pour garantir une représentation précise, si la pile est vide, la position de l'index se voit attribuer -1 dans le vecteur représentant l'intervalle actuel. Cela signifie qu'il n'y a pas d'intervalles qui ne se chevauchent pas sur la droite.

• Il est fortement recommandé de s'assurer que la pile que nous spécifions contient des éléments avant de tenter cette tâche, sinon une erreur se produira. Après avoir confirmé que nous avons un ou plusieurs éléments sur ladite structure, nous pouvons le faire en demandant au vecteur de l'intervalle actuel de définir sa valeur d'index sur la même valeur que l'élément correspondant en première position sur la structure que nous avons identifiée et ses informations d'index correspondantes. .Incluez-le dans la même structure pour effectuer des opérations.

• Répétez les étapes 3 à 7 jusqu'à ce que tous les intervalles aient été traités.

• Renvoie le vecteur d'index.

Méthode

Pour résoudre ce dilemme, nous examinerons deux stratégies différentes.

Méthode 1 : Fissuration par force brute

Une stratégie possible pour résoudre ce problème est de recourir à la violence. Essentiellement, cela nécessite d'examiner chaque intervalle individuel, puis de le comparer à tous les intervalles situés à sa droite jusqu'à ce qu'aucune option d'intersection ne devienne évidente. Cependant. Il convient de noter que l’utilisation de cette méthode entraîne une complexité temporelle de O(N^2). Où N représente le nombre total d'intervalles participant au processus d'inspection.

Grammaire

vector<int> findClosestNonOverlappingInterval(const vector<Interval>& intervals) {
   vector<int> result(intervals.size(), -1);
   for (int i = 0; i < intervals.size(); i++) {
      for (int j = i + 1; j < intervals.size(); j++) {
         if (intervals[i].end < intervals[j].start) {
            result[i] = j;
            break;
         }
      }
   }
   return result;
}

Exemple

Exemple

#include 
#include 

using namespace std;

// Define the Interval structure
struct Interval {
   int start;
   int end;
};

vector<int> findClosestNonOverlappingInterval(const vector<Interval>& intervals) {
   vector<int> result(intervals.size(), -1);
   for (int i = 0; i < intervals.size(); i++) {
      for (int j = i + 1; j < intervals.size(); j++) {
         if (intervals[i].end < intervals[j].start) {
            result[i] = j;
            break;
         }
      }
   }
   return result;
}

int main() {
   // Define intervals
   vector intervals = {{1, 3}, {2, 4}, {5, 7}, {6, 9}, {8, 10}};

   // Find the index of closest non-overlapping interval for each interval
   vector closestIndices = findClosestNonOverlappingInterval(intervals);

   // Print the results
   for (int i = 0; i < intervals.size(); i++) {
      cout << "Interval [" << intervals[i].start << ", " << intervals[i].end << "] ";
      if (closestIndices[i] != -1) {
         cout << "has closest non-overlapping interval at index " << closestIndices[i] << endl;
      } else {
         cout << "has no non-overlapping interval to the right" << endl;
      }
   }
   return 0;
}

Sortie

Interval [1, 3] has closest non-overlapping interval at index 2
Interval [2, 4] has closest non-overlapping interval at index 2
Interval [5, 7] has closest non-overlapping interval at index 4
Interval [6, 9] has no non-overlapping interval to the right
Interval [8, 10] has no non-overlapping interval to the right

Méthode 2 : Solution optimale

Une approche très efficace consiste à utiliser une pile comme moyen de surveiller les intervalles récents qui ne se chevauchent pas. La complexité temporelle de cette stratégie est O(N) puisque notre tâche ne nous oblige à parcourir l'intervalle qu'une seule fois.

Grammaire

vector<int> findClosestNonOverlappingInterval(const vector<Interval>& intervals) {
   vector<int> result(intervals.size(), -1);
   stack<int> st;
   for (int i = intervals.size() - 1; i >= 0; i--) {
      while (!st.empty() && intervals[i].end >= intervals[st.top()].start) {
         st.pop();
      }
      if (!st.empty()) {
         result[i] = st.top();
      }
      st.push(i);
   }
   return result;
}

Exemple

Exemple

#include 
#include 

using namespace std;

// Define the Interval structure
struct Interval {
   int start;
   int end;
};

vector<int> findClosestNonOverlappingInterval(const vector<Interval>& intervals) {
   vector<int> result(intervals.size(), -1);
   for (int i = 0; i < intervals.size(); i++) {
      for (int j = i + 1; j < intervals.size(); j++) {
         if (intervals[i].end < intervals[j].start) {
            result[i] = j;
            break;
         }
      }
   }
   return result;
}

int main() {
   // Define intervals
   vector intervals = {{1, 3}, {2, 4}, {5, 7}, {6, 9}, {8, 10}};
   
   // Find the index of closest non-overlapping interval for each interval
   vector closestIndices = findClosestNonOverlappingInterval(intervals);
   
   // Print the results
   for (int i = 0; i < intervals.size(); i++) {
      cout << "Interval [" << intervals[i].start << ", " << intervals[i].end << "] ";
      if (closestIndices[i] != -1) {
         cout << "has closest non-overlapping interval at index " << closestIndices[i] << endl;
      } else {
         cout << "has no non-overlapping interval to the right" << endl;
      }
   }
   return 0;
}

Sortie

Interval [1, 3] has closest non-overlapping interval at index 2
Interval [2, 4] has closest non-overlapping interval at index 2
Interval [5, 7] has closest non-overlapping interval at index 4
Interval [6, 9] has no non-overlapping interval to the right
Interval [8, 10] has no non-overlapping interval to the right

Conclusion

Notre objectif d'exploration est de trouver la meilleure position de l'index d'intervalle non chevauchant le plus proche à droite de chaque intervalle donné en C++. Tout d’abord, nous discutons en profondeur de la complexité syntaxique, tout en proposant un algorithme et en proposant deux solutions potentielles. Dans le cadre de notre enquête, nous montrons comment notre approche par force brute et notre approche d'optimisation basée sur la pile fonctionnent avec du code exécutable testé avec succès. Cette méthode vous permet d'identifier facilement les intervalles non chevauchants les plus proches pour un ensemble particulier.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!