-
Notifications
You must be signed in to change notification settings - Fork 9
/
intervals Merge Overlapping
61 lines (51 loc) · 1.17 KB
/
intervals Merge Overlapping
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
struct Interval
{
int start, end;
};
bool compareInterval(Interval i1, Interval i2)
{
return (i1.start < i2.start);
}
void mergeIntervals(Interval arr[], int n)
{
if (n <= 0)
return;
// Create an empty stack of intervals
stack<Interval> s;
sort(arr, arr+n, compareInterval);
s.push(arr[0]);
// 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 < arr[i].start)
s.push(arr[i]);
// Otherwise update the ending time of top if ending of current interval is more
else if (top.end < arr[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;
}
int main()
{
Interval arr[] = { {6,8}, {1,9}, {2,4}, {4,7} };
int n = sizeof(arr)/sizeof(arr[0]);
mergeIntervals(arr, n);
return 0;
}