Finden Sie den Index des nächstgelegenen nicht überlappenden Intervalls rechts von jedem der angegebenen N Intervalle

Eine Standardintervalldarstellung umfasst normalerweise einen Satz gepaarter Start- und Endpunkte. Unser aktuelles Dilemma besteht darin, das nächste nicht überlappende Intervall rechts von jedem angegebenen Intervall zu finden. Diese Aufgabe ist in vielen verschiedenen Anwendungen wie der Ressourcenzuweisung und -planung von großer Bedeutung, da es darum geht, das nächste Intervall zu identifizieren, das das aktuelle Intervall nicht schneidet oder enthält.

Grammatik

Um die Codedemonstration, die wir gleich zeigen werden, besser zu verstehen, werfen wir zunächst einen Blick auf die Syntax, die wir verwenden werden, bevor wir uns mit dem Algorithmus befassen.

// 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>

Algorithmus

Um dieses Problem zu lösen, ist ein organisierter Ansatz erforderlich, der sich auf die Iteration von Intervallen in umgekehrter Reihenfolge konzentriert und gleichzeitig einen Stapel von Indizes verwaltet, die auf die nächstgelegenen, nicht überlappenden Partner verweisen. Hier sind die kurzen, aber effektiven Schritte, wie unser vorgeschlagener Algorithmus dieses Problem löst -

• Erstellen Sie einen leeren Stapel, um die Indizes nicht überlappender Bereiche zu speichern.

• Initialisieren Sie einen Indexvektor mit einer Größe, die der Anzahl der Intervalle entspricht, aufgefüllt mit -1, um anzuzeigen, dass kein nicht überlappendes Intervall gefunden wurde.

• Durchlaufen Sie die Intervalle von rechts nach links.

• Wenn der Stapel nicht leer ist und zwischen dem aktuellen Intervall und dem oberen Intervall eine Querschnittsfläche vorhanden ist, fahren Sie fort, den obersten Index aus dem Stapel zu entfernen (zu entfernen).

• Um eine genaue Darstellung zu gewährleisten, wird der Indexposition bei leerem Stapel -1 im Vektor zugewiesen, der das aktuelle Intervall darstellt. Das bedeutet, dass es rechts keine nicht überlappenden Intervalle gibt.

• Es wird dringend empfohlen, sicherzustellen, dass der von uns angegebene Stapel Elemente enthält, bevor diese Aufgabe ausgeführt wird. Nachdem wir bestätigt haben, dass wir ein oder mehrere Elemente in dieser Struktur haben, können wir dies tun, indem wir den Indexwert des Vektors des aktuellen Intervalls auf den gleichen Wert wie das entsprechende Element an der obersten Position in der von uns identifizierten Struktur und seine entsprechenden Indexinformationen setzen . Fügen Sie es in dieselbe Struktur ein, um Operationen auszuführen.

• Wiederholen Sie die Schritte 3-7, bis alle Intervalle abgearbeitet sind.

• Gibt den Indexvektor zurück.

Methode

Um dieses Dilemma zu lösen, werden wir uns zwei verschiedene Strategien ansehen.

Methode 1: Brute-Force-Cracking

Eine mögliche Strategie zur Lösung dieses Problems ist der Einsatz von Gewalt. Im Wesentlichen erfordert dies die Untersuchung jedes einzelnen Intervalls und den anschließenden Vergleich mit allen Intervallen rechts davon, bis keine Schnittoption mehr offensichtlich wird. Jedoch. Es ist erwähnenswert, dass die Verwendung dieser Methode zu einer zeitlichen Komplexität von O(N^2) führt. Wobei N die Gesamtzahl der am Inspektionsprozess beteiligten Intervalle darstellt.

Grammatik

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;
}

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#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;
}

Ausgabe

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

Methode 2: Optimale Lösung

Ein sehr erfolgreicher Ansatz besteht darin, einen Stapel als Mittel zur Überwachung aktueller, sich nicht überlappender Intervalle zu verwenden. Die zeitliche Komplexität dieser Strategie beträgt O(N), da unsere Aufgabe nur erfordert, dass wir das Intervall einmal durchgehen.

Grammatik

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;
}

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#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;
}

Ausgabe

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

Fazit

Unser Forschungsziel besteht darin, die beste Position des nächsten nicht überlappenden Intervallindex rechts von jedem gegebenen Intervall in C++ zu finden. Zunächst besprechen wir die syntaktische Komplexität eingehend, schlagen einen Algorithmus und zwei mögliche Lösungen vor. Im Rahmen unserer Untersuchung zeigen wir, wie unser Brute-Force-Ansatz und der stapelbasierte Optimierungsansatz mit erfolgreich getestetem ausführbarem Code funktionieren. Mit dieser Methode können Sie ganz einfach die nächstgelegenen, sich nicht überlappenden Intervalle für einen bestimmten Satz identifizieren.

Das obige ist der detaillierte Inhalt vonFinden Sie den Index des nächstgelegenen nicht überlappenden Intervalls rechts von jedem der angegebenen N Intervalle. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!