A funny O(n*log(n)) solution using segment tree

• O(n * log(n)) time complexity.
O(n) space complexity.

``````#include <algorithm>
#include <iostream>
#include <vector>

struct Solution {
std::vector<Interval> merge(std::vector<Interval>& intervals)
{
if (intervals.empty())
return intervals;
std::vector<int> values;
for (auto& iv : intervals) {
values.push_back(iv.start);
values.push_back(iv.end);
}
std::sort(values.begin(), values.end());
n = std::unique(values.begin(), values.end()) - values.begin();
values.resize(n);
tree.resize(n * 4 + 10);
mergelr.resize(n * 4 + 10);
for (auto& iv : intervals) {
segtree_set(
std::lower_bound(values.begin(), values.end(), iv.start) - values.begin() + 1,
std::lower_bound(values.begin(), values.end(), iv.end) - values.begin() + 1
);
}
auto ans = segtree_getall();
for (auto& iv : ans) {
iv.start = values[iv.start - 1];
iv.end = values[iv.end - 1];
}
return ans;
}

void segtree_set(int _ql, int _qr)
{
ql = _ql;
qr = _qr;
segtree_setr(1, 1, n);
}

std::vector<Interval> segtree_getall()
{
return segtree_get(1, 1, n);
}

void segtree_setr(int node, int first, int last)
{
if (tree[node] == 1)
return;
if (ql <= first && qr >= last) {
mergelr[node] = 1;
tree[node] = 1;
return;
}
int mid = first + (last - first) / 2;
int lch = node * 2;
int rch = node * 2 + 1;
if (ql <= mid && qr > mid)
mergelr[node] = 1;
if (ql <= mid)
segtree_setr(lch, first, mid);
if (qr > mid)
segtree_setr(rch, mid + 1, last);
if (tree[lch] && tree[rch] && mergelr[node])
tree[node] = 1;
}

std::vector<Interval> segtree_get(int node, int first, int last)
{
if (tree[node] == 1)
return {Interval{first, last}};
if (first == last)
return {};
int mid = first + (last - first) / 2;
auto lans = segtree_get(node * 2, first, mid);
auto rans = segtree_get(node * 2 + 1, mid + 1, last);
if (lans.size() && rans.size() && mergelr[node]) {
int nstart = lans.back().start;
int nend = rans.front().end;
lans.pop_back();
lans.push_back(Interval{nstart, nend});
lans.insert(lans.end(), rans.begin() + 1, rans.end());
} else {
lans.insert(lans.end(), rans.begin(), rans.end());
}
return lans;
}

int n;
int ql, qr;
std::vector<int> tree; // whether the whole segment is covered
std::vector<int> mergelr; // whether [mid, mid + 1] is covered
};
``````

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