I share this solution because my friend was asked in his FB interview. He was asked to do it without sorting, for a large stream of intervals. The solution can be interval tree, but that is too complicated. Here I maintain a BST of distinct intervals. We dont need to maintain all the intervals like interval tree. We will merge intervals while we inserting. The code did not balance the tree. That is why performance is still 500+ms.

Suppose we already have a BST of disjoint intervals. Given a new interval A, it will first find the toppest interval that has overlapping with A. Suppose it is B. Until now everything is easy. We simply traversed tree to reach this.

Then, it will try to expand interval B. Now it becomes tricky. There are 3 cases. 1 case is simple. For the other 2 cases, you will need to delete currentNode, because it is already merged. You need to always correctly maintain prevNode and direction, in order to merge correctly in next round. For 1 case, you can end there. For another case, you need to continue exploration.

The 2nd and 3rd case have duplicate code. However, I just keep it for better understanding.

The whole reason we can do this, is because: we will never meet a situation that we delete 1 node with 2 children but still keep its 2 children. If we remove 1 node, that means either his left or right is deleted. So, this is not really traditional node deletion in BST!!!!!!

I only share my code that insert a new interval to a BST. Other parts are simple.

Please see notes when we exploring left Children, comments are omitted when exploring right children.

```
void InsertInterval(BSTInterval *node, Interval ¤tInterval, BSTInterval *prev, int sign){
//sign=1 if prev->left = node, sign=-1 if prev->right=node.
int start=currentInterval.start, end = currentInterval.end;
if(node==NULL){
BSTInterval *newnode = new BSTInterval(start, end);
if(sign==1){
prev->left = newnode;
return;
}
else{
prev->right = newnode;
return;
}
}
if (node->start<=start && node->end>=end)
return;
if (node->start>end){
InsertInterval(node->left, currentInterval, node, 1);
return;
}
if (node->end<start){
InsertInterval(node->right, currentInterval, node, -1);
return;
}
/* Now we find the node that overlap with the interval we want to insert.
We start from here and merge intervals. */
//newLeft is always the new start after explore.
int newLeft=min(start, node->start);
if(start<node->start){
BSTInterval * currentNode = node;
BSTInterval * prevNode = NULL;
while(currentNode != NULL){
if (newLeft>currentNode->end){
//apparently need to explore right direction.
prevNode = currentNode;
currentNode = currentNode->right;
sign = -1;
}
else if (newLeft>currentNode->start){
//apparently currentNode is not node, otherwise will not hit here
//so, it is safe to delete currentNode
//also, in this case, no need to explore more nodes, why?
newLeft=currentNode->start;
clear(currentNode->right);
currentNode->right=NULL;
if(sign==1)
prevNode->left = currentNode->left;
else
prevNode->right = currentNode->left;
//we don't need to explore.
delete currentNode;
break;//no need to continue, why?
}
else{
//be careful: currentNode will be deleted if it is not node
//then, we need to update prevNode and sign directly
//otherwise we can not properly delete next node!!!
//this case still needs exploration.
BSTInterval *leftChild = currentNode->left;
if(currentNode!=node){
//prevNode and sign not changed. Just delete currentNode
clear(currentNode->right);
currentNode->right=NULL;
if(sign==1)
prevNode->left = leftChild;
else
prevNode->right = leftChild;
delete currentNode;
}
else{
//prevNode and sign changed.
prevNode = currentNode;
sign = 1;
}
currentNode=leftChild;
}
}
}
node->start = newLeft;
int newRight=max(end, node->end);
if(end>node->end){
BSTInterval * currentNode = node;
BSTInterval * prevNode = NULL;
while(currentNode != NULL){
if (newRight<currentNode->start){
prevNode = currentNode;
currentNode = currentNode->left;
sign = +1;
}
else if (newRight<currentNode->end){
newRight=currentNode->end;
clear(currentNode->left);
currentNode->left=NULL;
if(sign==1)
prevNode->left = currentNode->right;
else
prevNode->right = currentNode->right;
delete currentNode;
break;
}
else{
BSTInterval *rightChild = currentNode->right;
if(currentNode!=node){
clear(currentNode->left);
currentNode->left=NULL;
if(sign==1)
prevNode->left = rightChild;
else
prevNode->right = rightChild;
delete currentNode;
}
else{
prevNode = currentNode;
sign = -1;
}
currentNode=rightChild;
}
}
}
node->end = newRight;
return;
```

}