数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
