英文:
Merging Overlapping Intervals using Stack<pair<int,int>>
问题
I am merging overlapping intervals like
5 12, 1 8, 14 19, 22 28, 25 27, 27 30
So, use the logic using the pair<int, int> template. But I can't push pair elements into the Stack<pair<int, int>>, because I'm pushing (&int, &int) instead of (int, int). So, what should I do?
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
void mergeOverlappingIntervals(vector<vector<int>> &arr) {
vector<pair<int, int>> v;
for(int i=0; i<arr.size(); i++) {
v.push_back(make_pair(arr[i][0], arr[i][1]));
}
sort(v.begin(), v.end());
stack<pair<int, int>> st;
st.push(v[0]);
for(int i=1; i<v.size(); i++) {
pair<int, int> top = st.top();
if(v[i].first <= top.second) {
top.second = max(top.second, v[i].second);
st.pop();
st.push(top);
}
else {
st.push(v[i]);
}
}
while(!st.empty()) {
pair<int, int> top = st.top();
cout << top.first << " " << top.second << endl;
st.pop();
}
}
int main() {
int n;
cin >> n;
vector<vector<int>> arr(n, vector<int>(2, 0));
for(int i=0; i<n; i++) {
cin >> arr[i][0];
cin >> arr[i][1];
}
mergeOverlappingIntervals(arr);
return 0;
}
Note: I have corrected the code to properly push and pop pairs in the stack, and also fixed some syntax issues.
英文:
I am merging overlapping intervals like
> 5 12, 1 8, 14 19, 22 28, 25 27, 27 30
So, use the logic using the pair<int, int> template. But I can't push pair elements into the Stack<pair<int, int>>, because I'm pushing (&int, &int) instead of (int, int). So, what should I do?
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
void mergeOverlappingIntervals(vector<vector<int>> &arr) {
vector<pair<int, int>> v;
for(int i=0; i<arr.size(); i++) {
v.push_back(make_pair(arr[i][0], arr[i][1]));
}
sort(v.begin(), v.end());
// for(auto x:v) {
// cout << x.first << " " << x.second << endl;
// }
stack<pair<int, int>> st;
st.push(v[0].first, v[0].second);
for(int i=1; i<v.size(); i++) {
int top = st.top();
if(v[i].first <= top.second) {
top.second = max(top.second, v[i].second);
}
st.push(v[i].first, v[i].second);
}
while(!st.empty()) {
int top = st.top();
cout << top.fist << " " << top.second << endl;
st.pop();
}
}
int main() {
int n;
cin >> n;
vector<vector<int>> arr(n, vector<int>(2, 0));
for(int i=0; i<n; i++) {
cin >> arr[i][0];
cin >> arr[i][1];
}
mergeOverlappingIntervals(arr);
return 0;
}
答案1
得分: 1
当我尝试编译时，我收到以下错误消息：
<source>：在函数'void mergeOverlappingIntervals(std::vector<std::vector<int>> &)'中：
<source>：16:12：错误：没有匹配的函数用于'std::stack<std::pair<int, int>>::push(int&, int&)'
16 | st.push(v[0].first,v[0].second);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
在文件/opt/compiler-explorer/gcc-12.2.0/include/c++/12.2.0/stack中包括，来自<source>：4的：
/opt/compiler-explorer/gcc-12.2.0/include/c++/12.2.0/bits/stl_stack.h：260：7：注释：候选：'void std::stack<_Tp, _Sequence>::push(const value_type&)' [with _Tp = std::pair<int, int>; _Sequence = std::deque<std::pair<int, int>, std::allocator<std::pair<int, int>>; value_type = std::pair<int, int>]
260 | push(const value_type& __x)
| ^~~~
[...]
这是因为std::stack< std::pair<int,int> >::push只接受一个参数，而不是两个。你可以在这里找到文档：https://en.cppreference.com/w/cpp/container/stack/push
你可以像在向向量推送时那样使用std::make_pair。实际上，向向量推送类似于向堆栈推送。尽管在这两种情况下都不需要std::make_pair。只需添加一对{}来构造该对：
st.push({v[i].first,v[i].second});
或者，你可以使用emplace。它会接受参数，然后将其转发给元素的构造函数。
英文:
You must have misunderstood the error message. As you did not include it, I cannot explain it to you.
When I try to compile I get following error message:
<source>: In function 'void mergeOverlappingIntervals(std::vector<std::vector<int> >&)':
<source>:16:12: error: no matching function for call to 'std::stack<std::pair<int, int> >::push(int&, int&)'
16 | st.push(v[0].first,v[0].second);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /opt/compiler-explorer/gcc-12.2.0/include/c++/12.2.0/stack:61,
from <source>:4:
/opt/compiler-explorer/gcc-12.2.0/include/c++/12.2.0/bits/stl_stack.h:260:7: note: candidate: 'void std::stack<_Tp, _Sequence>::push(const value_type&) [with _Tp = std::pair<int, int>; _Sequence = std::deque<std::pair<int, int>, std::allocator<std::pair<int, int> > >; value_type = std::pair<int, int>]'
260 | push(const value_type& __x)
| ^~~~
[...]
And this is because std::stack< std::pair<int,int> >::push has a single parameter, not two. You can find documentation here: https://en.cppreference.com/w/cpp/container/stack/push
You could use std::make_pair as you did when pushing to the vector. Actually pushing to the vector is analogous to pushing to the stack. Though you do not need std::make_pair in either case. Just add a pair of {} to construct the pair:
st.push({v[i].first,v[i].second});
Alternatively you can use emplace. It does take parameters that are then forwarded to the elements constructor.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论