C++ implementation using interval tree


  • 3
    A

    The first response I had was to use an interval tree. But it may be overkill for this question.

    struct Node {
        Interval itv;
        int max;
        Node *left;
        Node *right;
        Node() : max(0), left(NULL), right(NULL) {}
        Node(const Interval &i) : itv(i), max(i.end), left(NULL), right(NULL) {}
    };
    
    bool canAttendMeetings(vector<Interval>& intervals) {
        Node *root = NULL;
        bool result = true;
        for (int i = 0; i < intervals.size(); i++) {
            if (root == NULL) {
                root = buildTree(intervals[i]);
            }
            else {
                if (searchTree(root, intervals[i])) {
                    result = false;
                    break;
                }
                addNode(root, intervals[i]);
            }
        }
        
        deleteTree(root);
        return result;
    }
    
    Node *buildTree(const Interval &i) {
        Node *root = new Node(i);
        return root;
    }
    
    void deleteTree(Node *root) {
        if (root) {
            if (root->left) {
                deleteTree(root->left);
                root->left = NULL;
            }
            if (root->right) {
                deleteTree(root->right);
                root->right = NULL;
            }
            delete root;
        }
    }
    
    void addNode(Node *root, const Interval &i) {
        if (root->left && i.start < root->itv.start) {
            addNode(root->left, i);
            if (root->left->max > root->max)
                root->max = root->left->max;
        }
        else if (root->right && i.start >= root->itv.start) {   
            addNode(root->right, i);
            if (root->right->max > root->max)
                root->max = root->right->max;
        }
        else {    
            Node *n = new Node(i);
            if (i.start < root->itv.start)
                root->left = n;
            else
                root->right = n;
            
            if (n->max > root->max)
                root->max = n->max;
        }
    }
    
    bool searchTree(const Node *root, const Interval &i) {
        const Node *node = root;
        while (node && !overlap(node->itv, i)) {
            if (node->left && node->left->max > i.start)
                node = node->left;
            else
                node = node->right;
        }
        if (node) return true;
        else return false;
    }
    
    bool overlap(const Interval &a, const Interval &b) {
        if (a.start < b.end && b.start < a.end)
            return true;
        return false;    
    }

  • -1
    T

    Like your OverKill!!!!!!!! lol


Log in to reply
 

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