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


  • 0
    L

    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
    };
    

Log in to reply
 

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