查找给定 N 个间隔右侧最近的非重叠间隔的索引
间隔的标准表示通常需要一组成对排列的起点和终点。查找每个指定间隔右侧最近的非重叠间隔是我们当前的难题。这项任务在许多不同的应用中具有重要意义，例如资源分配和调度，因为它涉及识别不与当前间隔相交或不包含当前间隔的后续间隔。
语法
为了帮助理解即将到来的代码演示，让我们首先检查一下在深入研究算法之前将要使用的语法 -
// 定义间隔结构
struct Interval {
int start;
int end;
};
// 查找最近非重叠间隔索引的函数
vector findClosestNonOverlappingInterval(const vector& intervals) {
// 实现在此处
}
算法
解决这个问题需要一种有组织的方法，该方法以反向顺序遍历间隔为中心，同时维护指向其最近非重叠伙伴的索引堆栈。以下是简要但有效的步骤，概述了我们提出的算法如何解决这个问题 -
创建一个空堆栈来存储非重叠间隔的索引。
初始化一个索引向量，其大小等于间隔数，用 -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;
// 定义 Interval 结构
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() {
// 定义间隔
vector<Interval> intervals = {{1, 3}, {2, 4}, {5, 7}, {6, 9}, {8, 10}};
// 查找每个间隔的最近非重叠间隔的索引
vector<int> nearestIndices = findClosestNonOverlappingInterval(intervals);
// 打印结果
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;
// 定义 Interval 结构
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() {
// 定义间隔
vector<Interval> intervals = {{1, 3}, {2, 4}, {5, 7}, {6, 9}, {8, 10}};
// 找到每个间隔的最近非重叠间隔的索引
vector<int> closestIndices = findClosestNonOverlappingInterval(intervals);
// 打印结果
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++ 中最好地找到每个给定间隔的最近非重叠间隔索引（位于其右侧）。首先，我们深入讨论了语法的复杂性，同时提出了一种算法并提出了两种可能的解决方案。作为我们调查的一部分，我们展示了我们的强力方法和基于堆栈的优化方法如何通过成功测试的可执行代码运行。这种方法使您能够轻松识别任何特定集合的最近非重叠间隔。
