[Geeks for Geeks] Overlapping Intervals

Overlapping Intervals

Given a collection of Intervals, the task is to merge all of the overlapping Intervals.

  • Time : O(nlogn)
  • Space : O(n)
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
class Solution {
map<int, int> intervals;
map<int, int>::iterator front(int s) {
auto it = intervals.upper_bound(s);
if(it == begin(intervals))
return intervals.insert({s,s}).first;
--it;
if(it->second >= s)
return it;
return intervals.insert({s,s}).first;
}
void merge(int s, int e) {
auto start = front(s);
start->second = max(start->second, e);
while(next(start) != end(intervals)) {
auto nxt = next(start);
if(start->second >= nxt->first) {
start->second = max(start->second, nxt->second);
intervals.erase(nxt);
} else break;
}
}
public:
vector<vector<int>> overlappedInterval(vector<vector<int>> &ranges) {
for(auto& range : ranges) {
merge(range[0], range[1]);
}
vector<vector<int>> res;
for(auto interval : intervals) {
res.push_back({interval.first, interval.second});
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/15/PS/GeeksforGeeks/overlapping-intervals/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.