### SKYLINE PROBLEM

Problem-Given starting point (x),ending point(y) and height(h) of a several overlapping buildings.Our task is find the outline of all buildings as shown in picture.

///////////////////////////////////////////////////////////////////////////////

Approach-Problem can be solved by using LINE SWEEP algorithm.

//Code starts here
``````#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > getSkyline(vector<vector<int> >& buildings) {
int lent = buildings.size();
int a,b,c;
vector<vector<int> > answ;
pair<int,int> p1;
vector<pair<int,int> > vec;
for(int i=0;i<lent;i++){
a=buildings[i][0];
b=buildings[i][1];
c=buildings[i][2];
p1.first=a;
p1.second=c;
vec.push_back(p1);
p1.first=b;
p1.second=((-1)*(c));
vec.push_back(p1);
}/////
sort(vec.begin(),vec.end());
// cout<<"The Sorted Vector is "<<endl;
// for(int y=0;y<vec.size();y++){
// cout<<vec[y].first<<"  "<<vec[y].second<<endl;
// }

map<int,int,greater<int> > m1;
map<int,int>::iterator itr,ittr,itl,itx;
m1.insert(make_pair(0,1000));
int fir,sec,fir2;
int prev=0;
vec.push_back(make_pair(-1,-1));
for(int z=0;z<(vec.size()-1);z++){
fir=vec[z].first;
sec=vec[z].second;
fir2=vec[z+1].first;

// cout<<"The first part is "<<fir<<endl;
// cout<<"The second part is "<<sec<<endl;
// cout<<"The Map Before Modification is"<<endl;
// for(itl=m1.begin();itl!=m1.end();itl++){
// cout<<itl->first<<" "<<itl->second<<endl;
// }
// cout<<"************************"<<endl;
if(sec<0){
m1[abs(sec)]--;
if(m1[abs(sec)]==0){
itx=m1.find(abs(sec));
m1.erase(itx);
// cout<<"I have erased "<<sec<<endl;
}
// cout<<"The Map After Modification is"<<endl;
// for(itl=m1.begin();itl!=m1.end();itl++){
// cout<<itl->first<<" "<<itl->second<<endl;
// }
// cout<<"************************"<<endl;
if(fir!=fir2){

ittr=m1.begin();
if((ittr->first)!=prev){
// cout<<fir<<" "<<ittr->first<<endl;
vector<int> tte;
tte.push_back(fir);
tte.push_back(ittr->first);
answ.push_back(tte);
prev=ittr->first;
}
}
}/////////////////
else{
itr=m1.find(sec);
if(itr!=m1.end()){
m1[sec]++;

// cout<<"The Map After Modification is"<<endl;
// for(itl=m1.begin();itl!=m1.end();itl++){
// cout<<itl->first<<" "<<itl->second<<endl;
// }
// cout<<"************************"<<endl;
if(fir!=fir2){

ittr=m1.begin();
if(ittr->first!=prev){
//cout<<fir<<" "<<ittr->first<<endl;
vector<int> tte;
tte.push_back(fir);
tte.push_back(ittr->first);
answ.push_back(tte);
prev=ittr->first;
}
}
}
else{
m1.insert(make_pair(sec,1));

// cout<<"The Map After Modification is"<<endl;
// for(itl=m1.begin();itl!=m1.end();itl++){
// cout<<itl->first<<" "<<itl->second<<endl;
// }
// cout<<"************************"<<endl;
if(fir!=fir2){

ittr=m1.begin();
if(ittr->first!=prev){
//cout<<fir<<" "<<ittr->first<<endl;
vector<int> tte;
tte.push_back(fir);
tte.push_back(ittr->first);
answ.push_back(tte);
prev=ittr->first;
}
}
}
}

}
return answ;
//for(int ll=0;ll<answ.size();ll++){
// cout<<answ[ll][0]<<" "<<answ[ll][1]<<endl;
//}
}

int main(){
vector<vector<int> > buildings;
int mm;
cout<<"Enter the Number of Buildings "<<endl;
cin>>mm;
int x,y,z;
for(int h=0;h<mm;h++){
cout<<"Enter the left  right and height  coordinates "<<endl;
cin>>x>>y>>z;
vector<int> vec;
vec.push_back(x);
vec.push_back(y);
vec.push_back(z);
buildings.push_back(vec);
}
vector<vector<int> > outline = getSkyline(buildings);
}``````