<p>You are given a 2D integer array <code>intervals</code> where <code>intervals[i] = [left<sub>i</sub>, right<sub>i</sub>]</code> represents the <strong>inclusive</strong> interval <code>[left<sub>i</sub>, right<sub>i</sub>]</code>.</p>

<p>You have to divide the intervals into one or more <strong>groups</strong> such that each interval is in <strong>exactly</strong> one group, and no two intervals that are in the same group <strong>intersect</strong> each other.</p>

<p>Return <em>the <strong>minimum</strong> number of groups you need to make</em>.</p>

<p>Two intervals <strong>intersect</strong> if there is at least one common number between them. For example, the intervals <code>[1, 5]</code> and <code>[5, 8]</code> intersect.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can divide the intervals into the following groups:
- Group 1: [1, 5], [6, 8].
- Group 2: [2, 3], [5, 10].
- Group 3: [1, 10].
It can be proven that it is not possible to divide the intervals into fewer than 3 groups.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> intervals = [[1,3],[5,6],[8,10],[11,13]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> None of the intervals overlap, so we can put all of them in one group.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 10<sup>5</sup></code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>1 &lt;= left<sub>i</sub> &lt;= right<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
</ul>

class Node:
    def __init__(self, interval, left=None, right=None, parent=None):
        self.interval = interval
        self.left = left
        self.right = right
        self.parent = parent


class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        def build_bst(intervals, start, length):
            if length == 0:
                return None

            root = Node(
                intervals[start + length // 2],
                build_bst(intervals, start, length // 2),
                build_bst(intervals, start + length // 2 + 1, length - length // 2 - 1))

            if root.left:
                root.left.parent = root
            if root.right:
                root.right.parent = root

            return root

        def find_minimum_larger(root, interval):
            if not root:
                return None

            # find the node with minimum start that is > end of given intervals
            cur = root
            while cur.interval[0] <= interval[1]:
                if cur.right:
                    cur = cur.right
                else:
                    return None
            
            cand = find_minimum_larger(cur.left, interval)
            if cand:
                return cur if cur.interval[0] < cand.interval[0] else cand
            else:
                return cur

        def group(interval):
            # recursively group

            cur = find_minimum_larger(self.root, interval)
            if not cur:
                return

            # cur.interval won't be the given interval
            group(cur.interval)
            # group cur, so delete it
            delete_node(cur)
        
        def delete_node(node):
            if not node.left and not node.right:
                # leaf
                if node.parent:
                    if node == node.parent.left:
                        node.parent.left = None
                    else:
                        node.parent.right = None
                else:
                    # only a node in the tree
                    self.root = None

            elif node.left and not node.right:
                # only has left child
                node.left.parent = node.parent
                if node.parent:
                    if node == node.parent.left:
                        node.parent.left = node.left
                    else:
                        node.parent.right = node.left
                else:
                    # the node is root
                    self.root = node.left

            elif not node.left and node.right:
                # only has right child
                node.right.parent = node.parent
                if node.parent:
                    if node == node.parent.left:
                        node.parent.left = node.right
                    else:
                        node.parent.right = node.right
                else:
                    # the node is root
                    self.root = node.right

            else:
                # has left and right childs
                # replace node with the biggest node in left child
                replace = node.left
                while replace.right:
                    replace = replace.right

                # root won't change
                delete_node(replace)

                # replace may be node.left or node.right
                if node.left:
                    node.left.parent = replace
                if node.right:
                    node.right.parent = replace
                replace.left = node.left
                replace.right = node.right

                replace.parent = node.parent
                if node.parent:
                    if node.parent.left == node:
                        node.parent.left = replace
                    else:
                        node.parent.right = replace
                else:
                    # the node is root
                    self.root = replace

        intervals.sort(key=lambda x: x[0])
        # build BST
        self.root = build_bst(intervals, 0, len(intervals))

        ret = 0
        while True:
            # group other nodes with the leftmost node
            cur = self.root
            while cur.left:
                cur = cur.left

            group(cur.interval)
            ret += 1

            delete_node(cur)
            if not self.root:
                break

        return ret
1512