#include <iostream>
#include <vector>
using namespace std;

struct building {
	int l;		
	int h;		 
	int r;		
};
struct skyline {
	int x;
	int h;
};
void mergeSkylines ( auto &left, auto &right, auto &s ) {
	
	int i = 0, j = 0, h1 = 0, h2 = 0, h = 0;
	while ( i < left.size() && j < right.size() ) {
		if ( left[i].x < right[j].x ) {
			h1 = left[i].h;
			if ( max(h1, h2) != h ) {
				h = max(h1, h2);
				s.push_back ({left[i].x, h});
			}
			i++;
		}
		else {
			h2 = right[j].h;
			if ( max(h1, h2) != h ) {
				h = max (h1, h2);
				s.push_back ({right[j].x, h});
			}
			j++;
		}
	}
	while ( i < left.size() ) {
		if ( left[i].h != h ) {
			h = left[i].h;
			s.push_back ({left[i].x, h});
		}
		i++;
	}

	while ( j < right.size() ) {
		if ( right[j].h != h ) {
			h = right[j].h;
			s.push_back ({right[j].x, h});
		}
		j++;
	}
}
void formSkyline ( auto &b, int l, int r, auto &s ) {
	if ( l == r ) {
		// base case 
		s.push_back ({b[l].l, b[l].h});
		s.push_back ({b[l].r, 0});
	}
	else if ( l < r ) {
		int mid = (l + r) / 2;
		vector<skyline> left, right;
		formSkyline ( b, l, mid, left );
		formSkyline ( b, mid + 1, r, right );
		mergeSkylines ( left, right, s );
	}
}
int main ( ) {

	//vector<building> b = {{1, 5, 4}, {2, 6, 3}};
	vector<building> b = { {1,11,5}, {2,6,7}, {3,13,9}, {12,7,16}, {14,3,25}, {19,18,22}, {23,13,29}, {24,4,28} };
   vector<skyline> s;
   formSkyline ( b, 0, b.size() - 1, s );
   cout << "Resulting Skyline : \n";
   for ( auto i : s ) 
   	cout << "[" << i.x << " " << i.h << "] ";
	return 0;
}