c++ 32ms solution using simple linked list

• Main idea:
1 list node includes "begin","end","height","next","last",and each node's "end" equals the next node's "begin",
2 when we considering a new building, we first to find which two node including building's begin and end (may be one node),and then we reconsider the height of this nodes
3 in 2 we may need to split or merge some nodes
4 we put each node's begin and height as a pair to vector from head to tail
'''
class Solution {
public:
struct Node{
int begin;
int end;
int height;
Node* next;
Node* last;

``````    Node(int begin_,int end_,int height_): begin(begin_),end(end_),height(height_),next(NULL),last(NULL){}
};

void Split(Node* node,int bound){
Node* add = new Node(node->begin,bound,node->height);
node->begin = bound;
node->last->next = add;
add->last = node->last;
add->next = node;
node->last = add;
return ;
}

void Merge(Node* node){
if(node->height == node->last->height){
Node* old = node->last;
node->begin = old->begin;
old->last->next = node;
node->last = old->last;
delete(old);
}
return;
}
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> results;
int num = buildings.size();
if(num==0)
return results;
Node* head = new Node(0,0,0);
head->next = new Node(buildings[0][0],buildings[0][1],buildings[0][2]);
Node* tail = new Node(buildings[0][1],INT_MAX,0);
head->next->last = head;
head->next->next = tail;
tail->last = head->next;
Node* beginNode = head->next;
Node* endNode = NULL;

for(int i=1;i<num;i++){
int begin = buildings[i][0];
int end = buildings[i][1];
int height = buildings[i][2];

while(beginNode->end < begin)
beginNode = beginNode->next;

if(begin>beginNode->begin){
Split(beginNode,begin);
}

endNode = beginNode;
while(endNode->end < end)
endNode = endNode->next;

if(end < endNode->end){
Split(endNode,end);
if(endNode->last->begin == begin)
beginNode = endNode->last;
}else{
if(endNode!=tail)
endNode = endNode->next;
else{
endNode->next = new Node(end,INT_MAX,0);
endNode->next->last = endNode;
endNode = endNode->next;
tail = endNode;
}
}

Node* ptr;
for(ptr = beginNode;ptr!=endNode;ptr=ptr->next){
ptr->height = (ptr->height > height)? ptr->height:height;
Merge(ptr);
if(ptr->begin<=begin)
beginNode = ptr;
}
Merge(endNode);
if(endNode->begin<=begin)
beginNode = endNode;
}

Node* ptr;
int lastheight=-1;
for(ptr = head->next;ptr!=NULL;ptr = ptr->next){
if(ptr->height!=lastheight){
results.push_back(make_pair(ptr->begin,ptr->height));
lastheight = ptr->height;
}
}

return results;
}
``````

};
'''

• Really fast. I tried and it takes only 29 ms and beats 100%. However it is too long.

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