找到每个给定的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中文网其他相关文章！