Share a c++ version divide and conquer with running time 820ms


  • 3
    H

    It is inspired by the Java divide and conquer solution by hscaizh. Is there any trick to make the merge function smarter by using priority queue?

    vector<pair<int, int>> merge(vector<pair<int, int>> skyline1, vector<pair<int, int>> skyline2) {
        	vector<pair<int, int>> res;
        	//priority_queue<pair<int, int>> pq(skyline1.begin(), skyline1.end()); // first: x, second: h
        	//priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> pq(skyline1.begin(), skyline1.end()); // first: x, second: h
        	int len1=skyline1.size(), len2=skyline2.size(), cur1=0, cur2=0, cur1_H=-1, cur2_H=-1, cur_H, cur_X;
        	while(cur1<len1 && cur2<len2) {
        		if (skyline1[cur1].first<skyline2[cur2].first) {
        			cur_X=skyline1[cur1].first;
        			cur1_H=skyline1[cur1].second;
        			cur1++;
        		} else if (skyline1[cur1].first>skyline2[cur2].first) {
        			cur_X=skyline2[cur2].first;
        			cur2_H=skyline2[cur2].second;
        			cur2++;
        		} else {
        			cur_X=skyline1[cur1].first;
        			cur1_H=skyline1[cur1].second;
        			cur2_H=skyline2[cur2].second;
        			cur1++;
        			cur2++;
        		}
        		cur_H=max(cur1_H, cur2_H);
        		if (res.empty() || res.back().second != cur_H)
        			res.push_back(make_pair(cur_X, cur_H));
        	}
        	while(cur1<len1)
        		res.push_back(skyline1[cur1++]);
        	while(cur2<len2)
        		res.push_back(skyline2[cur2++]);
        	return res;
        }
        vector<pair<int, int>> getSkyline_rec(vector<vector<int>>& buildings, int start, int end) { // recursive
        	if (start<end) {
        		int mid=start+(end-start)/2;
        		return merge(getSkyline_rec(buildings, start, mid), getSkyline_rec(buildings, mid+1, end));
        	} else {
        		vector<pair<int, int>> res(2);
        		res[0]=make_pair(buildings[start][0], buildings[start][2]);
        		res[1]=make_pair(buildings[start][1], 0);
        		return res;
        	}
        }
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) { // 820ms, divide and conquer, _2
            if (buildings.empty()) return vector<pair<int,int>>();
        	return getSkyline_rec(buildings, 0, buildings.size()-1);
        }

Log in to reply
 

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