找到每個給定的N個區間右側最接近的非重疊區間的索引-C++-PHP中文網

找到每個給定的N個區間右側最接近的非重疊區間的索引

一個標準的區間表示通常包括一組成對排列的起始點和結束點。找到每個指定區間右側最近的不重疊區間構成了我們目前的困境。這個任務在許多不同的應用中具有巨大的重要性，例如資源分配和調度，因為它涉及識別不與當前區間相交或包含的下一個區間。

文法

為了幫助理解即將展示的程式碼演示，讓我們先查看將要使用的語法，然後再深入演算法。

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

登入後複製

演算法

解決這個問題需要一個有組織的方法，以逆序迭代區間為中心，同時維護一個指向它們最近的非重疊夥伴的索引堆疊。以下是我們提出的演算法如何解決這個問題的簡要但有效的步驟 -

建立一個空堆疊來儲存非重疊區間的索引。
使用與間隔數相等的大小初始化一個索引向量，並用-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;
}

登入後複製

Example

的中文翻譯為：

範例

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

登入後複製

輸出

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

登入後複製

方法二：最優解

一種非常成功的方法涉及利用堆疊作為監視最近的非重疊間隔的手段。此策略的時間複雜度為 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;
}

登入後複製

Example

的中文翻譯為：

範例

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

登入後複製

輸出

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 中找到每個給定區間右側最接近的非重疊區間索引的最佳位置。首先，我們深入討論了語法複雜性，同時提出了一個演算法並提出了兩種潛在解決方案。作為我們調查的一部分，我們展示了我們的蠻力方法和基於堆疊的最佳化方法如何透過成功測試的可執行程式碼來實現。這種方法使您能夠輕鬆地識別任何特定集合的最接近的非重疊區間。

以上是找到每個給定的N個區間右側最接近的非重疊區間的索引的詳細內容。更多資訊請關注PHP中文網其他相關文章！