Share my interval tree solution no sorting


  • 1
    H

    I want to do it without sorting, because:
    https://leetcode.com/discuss/67748/share-my-bst-interval-tree-solution-c-no-sorting?show=67748#q67748

    In that post, I used BST of intervals. However, as you can see from that post, if each node is an interval, it is very difficult to keep each node disjoint. Although that code achieved this, it is hard to read.

    So, I use interval tree in this post. You can google and find its variations, I am using the basic structure. Basically, each node will maintains a lot of intervals, depending on whether the interval intersect the middle of the node. It is easy to insert/delete an interval. The only difficult is: given an interval tree, how to get the final result, how to merge them in the final step?

    class IntervalTree{
    public:
        int middle;
        int start, end;
        IntervalTree *left, *right;
        IntervalTree(int s, int e): start(s), end(e), middle((s+e)/2){
            this->left=this->right=NULL;
        }
    

    };

    void InsertInterval(IntervalTree *node, Interval ¤tInterval){
    if(node == NULL)
        return;
    
    if(currentInterval.end<node->middle){
        if(node->left)
            return InsertInterval(node->left, currentInterval);
        else{
            IntervalTree *newnode = new IntervalTree(currentInterval.start, currentInterval.end);
            node->left = newnode;
            return;
        }
    }
    
    if(currentInterval.start>node->middle){
        if(node->right)
            return InsertInterval(node->right, currentInterval);
        else{
            IntervalTree *newnode = new IntervalTree(currentInterval.start, currentInterval.end);
            node->right = newnode;
            return;
        }
    }
    
    //insert it to current node
    node->start=min(node->start, currentInterval.start);
    node->end=max(node->end, currentInterval.end);
    

    }

    So, when you want to merge the intervals, you will do something like below:

    void QueryInterval(vector<Interval> &retV, IntervalTree *node){
    //retV is the return vector
    vector<Interval> leftIntervals;
    vector<Interval> rightIntervals;
    
    bool mergeleft = false; //whether current node merge with any intervals from left child. 
    if(node->left){
        //return the merge of all intervals in left child. 
        QueryInterval(leftIntervals, node->left);
        //merge left interval with myself. 
        MergeLeftInterval(leftIntervals, node, retV, mergeleft);
    }
    if(!mergeleft){ //if we did not merge left intervals, add a new one
        Interval newinterval;
        newinterval.start = node->start;
        newinterval.end = node->end;
        retV.push_back(newinterval);
    }
    
    if(node->right){
        QueryInterval(rightIntervals, node->right);
        MergeRightInterval(rightIntervals, node, retV);
    }
    
    return;
    

    }

    And finally, the 2 child functions used above:

    void MergeLeftInterval(vector<Interval> &leftIntervals, IntervalTree *node, vector<Interval> &retV, bool &merged){
    for(int i=0; i<leftIntervals.size(); i++){
        if(leftIntervals[i].end>=node->start){
            Interval newinterval;
            newinterval.start = min(leftIntervals[i].start, node->start);
            newinterval.end = node->end;
            retV.push_back(newinterval);
            merged = true;
            break;
        }
        else{
            retV.push_back(leftIntervals[i]);
        }
    }
    

    }

    void MergeRightInterval(vector<Interval> &rightIntervals, IntervalTree *node, vector<Interval> &retV){
    for(int i=0; i<rightIntervals.size(); i++){
    if(rightIntervals[i].start<=node->end){
    retV[retV.size()-1].end = max(rightIntervals[i].end, node->end);
    }
    else{
    retV.push_back(rightIntervals[i]);
    }
    }
    }


Log in to reply
 

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