資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢給定 N 個區間右側最近的非重疊區間的索引
區間的標準表示通常包含一組按對排列的起始點和結束點。查詢每個指定區間右側最近的非重疊區間構成了我們當前的難題。這項任務在許多不同的應用中具有重要意義，例如資源分配和排程，因為它涉及識別不與當前區間相交或包含當前區間的下一個區間。
語法
為了幫助理解即將到來的程式碼演示，讓我們首先檢查將在深入研究演算法之前使用的語法 -
// Define the Interval structure
struct Interval {
int start;
int end;
};
// Function to find the index of closest non-overlapping interval
vector findClosestNonOverlappingInterval(const vector& intervals) {
// Implementation goes here
}
演算法
解決此問題需要一種有組織的方法，該方法圍繞以相反的順序遍歷區間，同時維護一個索引堆疊，這些索引依次指向其最近的非重疊夥伴。以下是一些簡短但有效的步驟，概述了我們提出的演算法如何解決此問題 -
建立一個空棧來儲存非重疊區間的索引。
初始化一個大小等於區間數的索引向量，並填充 -1 以指示尚未找到非重疊區間。
從右到左遍歷區間。
如果棧不為空，並且當前區間和棧頂區間之間存在交叉區域，則繼續消除（彈出）該棧頂索引。
為了確保準確的表示，如果棧為空，則將向量中表示當前區間的索引位置的值賦值為 -1。這表示右側不存在非重疊區間。
強烈建議在嘗試此任務之前確保我們指定的棧有元素；否則，請預期會出現錯誤。在確認我們在該結構上有一個或多個元素後，我們可以透過讓當前區間的向量將其索引值設定為其在已識別結構上的最頂端位置的對應值，以及將其相應的索引資訊也包含到該結構上來繼續。
重複步驟 3-7，直到所有區間都已處理。
返回索引向量。
方法
為了解決這個難題，我們將研究兩種不同的策略。
方法 1：暴力法
解決此問題的一種可能策略涉及使用暴力法。從本質上講，這需要檢查每個單獨的區間，然後將其與位於其右側的所有區間進行比較，直到出現一個沒有交集的選項。但是。重要的是要承認，使用此方法會產生 O(N^2) 的時間複雜度。其中 N 表示參與檢查過程的區間總數。
語法
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;
}
示例
#include <iostream>
#include <vector>
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<Interval> intervals = {{1, 3}, {2, 4}, {5, 7}, {6, 9}, {8, 10}};
// Find the index of closest non-overlapping interval for each interval
vector<int> 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;
}
輸出
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
方法 2：最優解
一種非常成功的方法是使用棧作為監視最近非重疊區間的工具。此策略擁有 O(N) 的時間複雜度，因為我們的任務只需要遍歷區間一次。
語法
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;
}
示例
#include <iostream>
#include <vector>
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<Interval> intervals = {{1, 3}, {2, 4}, {5, 7}, {6, 9}, {8, 10}};
// Find the index of closest non-overlapping interval for each interval
vector<int> 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;
}
輸出
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
結論
我們的探索旨在揭示如何在 C++ 中最好地找到每個給定區間的最近非重疊區間索引，該索引位於其右側。首先，我們深入探討了語法細節，同時提出了演算法並提出了兩種可能的解決方案。作為我們調查的一部分，我們展示了我們的暴力方法和基於棧的最佳化方法是如何透過成功測試的可執行程式碼發揮作用的。此方法使您能夠輕鬆識別任何特定集合的最近非重疊區間。
92 次檢視
