使用Stack>合并重叠区间

huangapple
go评论95阅读模式
英文:

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?

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <stack>
  5. using namespace std;
  7. void mergeOverlappingIntervals(vector<vector<int>> &arr) {
  8.     vector<pair<int, int>> v;
  9.     for(int i=0; i<arr.size(); i++) {
  10.         v.push_back(make_pair(arr[i][0], arr[i][1]));
  11.     }
  12.     sort(v.begin(), v.end());
  13.     stack<pair<int, int>> st;
  14.     st.push(v[0]);
  15.     for(int i=1; i<v.size(); i++) {
  16.         pair<int, int> top = st.top();
  17.         if(v[i].first <= top.second) {
  18.             top.second = max(top.second, v[i].second);
  19.             st.pop();
  20.             st.push(top);
  21.         }
  22.         else {
  23.             st.push(v[i]);
  24.         }
  25.     }
  26.     while(!st.empty()) {
  27.         pair<int, int> top = st.top();
  28.         cout << top.first << " " << top.second << endl;
  29.         st.pop();
  30.     }
  31. }
  33. int main() {
  34.     int n;
  35.     cin >> n;
  36.     vector<vector<int>> arr(n, vector<int>(2, 0));
  37.     for(int i=0; i<n; i++) {
  38.         cin >> arr[i][0];
  39.         cin >> arr[i][1];
  40.     }
  41.     mergeOverlappingIntervals(arr);
  42.     return 0;
  43. }

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&lt;int, int> template. But I can't push pair elements into the Stack&lt;pair&lt;int, int>>, because I'm pushing (&int, &int) instead of (int, int). So, what should I do?

  1. #include &lt;iostream&gt;
  2. #include &lt;algorithm&gt;
  3. #include &lt;vector&gt;
  4. #include &lt;stack&gt;
  5. using namespace std;
  7. void mergeOverlappingIntervals(vector&lt;vector&lt;int&gt;&gt; &amp;arr) {
  8.     vector&lt;pair&lt;int, int&gt;&gt; v;
  9.     for(int i=0; i&lt;arr.size(); i++) {
  10.         v.push_back(make_pair(arr[i][0], arr[i][1]));
  11.     }
  12.     sort(v.begin(), v.end());
  13.     // for(auto x:v) {
  14.     //     cout &lt;&lt; x.first &lt;&lt; &quot; &quot; &lt;&lt; x.second &lt;&lt; endl;
  15.     // }
  16.     stack&lt;pair&lt;int, int&gt;&gt; st;
  17.     st.push(v[0].first, v[0].second);
  18.     for(int i=1; i&lt;v.size(); i++) {
  19.         int top = st.top();
  20.         if(v[i].first &lt;= top.second) {
  21.             top.second = max(top.second, v[i].second);
  22.         }
  23.         st.push(v[i].first, v[i].second);
  24.     }
  25.     while(!st.empty()) {
  26.         int top = st.top();
  27.         cout &lt;&lt; top.fist &lt;&lt; &quot; &quot; &lt;&lt; top.second &lt;&lt; endl;
  28.         st.pop();
  29.     }
  30. }
  32. int main() {
  33.     int n;
  34.     cin &gt;&gt; n;
  35.     vector&lt;vector&lt;int&gt;&gt; arr(n, vector&lt;int&gt;(2, 0));
  36.     for(int i=0; i&lt;n; i++) {
  37.         cin &gt;&gt; arr[i][0];
  38.         cin &gt;&gt; arr[i][1];
  39.     }
  40.     mergeOverlappingIntervals(arr);
  41.     return 0;
  42. }

答案1

得分: 1

当我尝试编译时，我收到以下错误消息：

  1. <source>：在函数'void mergeOverlappingIntervals(std::vector<std::vector<int>> &)'中：
  2. <source>：16:12：错误：没有匹配的函数用于'std::stack<std::pair<int, int>>::push(int&, int&)'
  3.    16 |     st.push(v[0].first,v[0].second);
  4.       |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
  5. 在文件/opt/compiler-explorer/gcc-12.2.0/include/c++/12.2.0/stack中包括，来自<source>：4的：
  6. /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>]
  7.   260 |       push(const value_type& __x)
  8.       |       ^~~~
  9. [...]

这是因为std::stack< std::pair<int,int> >::push只接受一个参数，而不是两个。你可以在这里找到文档：https://en.cppreference.com/w/cpp/container/stack/push

你可以像在向向量推送时那样使用std::make_pair。实际上，向向量推送类似于向堆栈推送。尽管在这两种情况下都不需要std::make_pair。只需添加一对{}来构造该对：

  1. 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:

  1. &lt;source&gt;: In function &#39;void mergeOverlappingIntervals(std::vector&lt;std::vector&lt;int&gt; &gt;&amp;)&#39;:
  2. &lt;source&gt;:16:12: error: no matching function for call to &#39;std::stack&lt;std::pair&lt;int, int&gt; &gt;::push(int&amp;, int&amp;)&#39;
  3.    16 |     st.push(v[0].first,v[0].second);
  4.       |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
  5. In file included from /opt/compiler-explorer/gcc-12.2.0/include/c++/12.2.0/stack:61,
  6.                  from &lt;source&gt;:4:
  7. /opt/compiler-explorer/gcc-12.2.0/include/c++/12.2.0/bits/stl_stack.h:260:7: note: candidate: &#39;void std::stack&lt;_Tp, _Sequence&gt;::push(const value_type&amp;) [with _Tp = std::pair&lt;int, int&gt;; _Sequence = std::deque&lt;std::pair&lt;int, int&gt;, std::allocator&lt;std::pair&lt;int, int&gt; &gt; &gt;; value_type = std::pair&lt;int, int&gt;]&#39;
  8.   260 |       push(const value_type&amp; __x)
  9.       |       ^~~~
  11. [...]

And this is because std::stack&lt; std::pair&lt;int,int&gt; &gt;::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:

  1. 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.

huangapple
  • 本文由 发表于 2023年2月6日 15:49:05
  • 转载请务必保留本文链接：https://go.coder-hub.com/75358579.html
  • c++
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定