# C++ Solution O(nlgn)

• ``````class Solution {
static bool sortfn(const Interval &a, const Interval &b) {
return a.start <= b.start;
}
struct cmpObject {
bool operator()(const Interval &a, const Interval &b) const {
return a.start <= b.start;
}
};
public:
vector<Interval> merge(vector<Interval>& intervals) {
sort(intervals.begin(), intervals.end(), Solution::sortfn);
priority_queue<Interval, vector<Interval>, cmpObject> pq;
for (auto &intvl : intervals ) {
if (pq.empty()) { pq.push(intvl); continue; }

auto top = pq.top();

// case 1 - non overlapping
if (intvl.start > top.end) {
pq.push(intvl);
continue;
}

// case 2 beg2 <= end1 and end2 > end
// merge and make a new intvl
// pop the top and push the new intvl
if (intvl.start <= top.end && intvl.end > top.end) {
Interval new_intvl(top.start, intvl.end);
pq.pop();
pq.push(new_intvl);
continue;
}

// case 3 new interval is completely within top interval
// skip it
}
cout << pq.size() << endl;
vector<Interval> ans;
while(!pq.empty()) {
auto top = pq.top();
ans.push_back(top);
pq.pop();
}
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
return ans;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.