I THINK PROBLEM IN MERGE FUNTION
1.Sort the intervals based on increasing order of starting time. 2. Push the first interval on to a stack. 3. For each interval do the following a. If the current interval does not overlap with the stack top, push it. b. If the current interval overlaps with stack top and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval. 4. At the end stack contains the merged intervals.
#include <iostream>
#include<vector>
#include<algorithm>
#include <stack>
using namespace std;
struct Interval
{
int start, end;
};
void mergeIntervals(vector<pair<int, int>> a, int n)
{
// Test if the given set has at least one interval
if (n <= 0)
return;
// Create an empty stack of intervals
stack<Interval> s;
// Start from the next interval and merge if necessary
for (int i = 1; i < n; i++)
{
// get interval from stack top
Interval top = s.top();
// if current interval is not overlapping with stack top,
// push it to the stack
if (top.end < a[i].start)
s.push(a[i]);
// Otherwise update the ending time of top if ending of current
// interval is more
else if (top.end < a[i].end)
{
top.end = arr[i].end;
s.pop();
s.push(top);
}
}
// Print contents of stack
cout<< "\n The Merged Intervals are: ";
while (!s.empty())
{
Interval t = s.top();
cout << "[" << t.start << "," << t.end << "] ";
s.pop();
}
return;
}
void print(vector<pair<int, int>> a) {
for (int i = 0; i < a.size(); i++) {
cout<<"{"<<a[i].first << "," << a[i].second<<"}"<<endl;
}
}
int main()
{
int n;
cout << "Enter Size of Interval : ";
cin >> n;
vector<pair<int, int> > a;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
a.push_back({ x, y });
}
cout << "Before Sorting : ";
print(a);
sort(a.begin(), a.end());
cout << "After Sorting : ";
print(a);
>I THINK PROBLEM IN MERGE FUNTION mergeIntervals(a, n);
return 0;
}
Aucun commentaire:
Enregistrer un commentaire