极客笔记C++ 找到给定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 ++中找到每个给定区间右侧最接近的非重叠区间索引。首先，我们探讨了语法细微差别，并提出了一个算法和两个潜在解决方案。作为调查的一部分，我们展示了我们的蛮力方法和基于堆栈的优化方法如何通过成功测试的可执行代码进行操作。这种方法使您可以轻松地识别任何特定集合的最接近的非重叠区间。