def interval_tree(intervals):
    """Construct an interval tree

    :param intervals: list of half-open intervals
                      encoded as value pairs [left, right)
    :assumes: intervals are lexicographically ordered
    :returns: the root of the interval tree
    :complexity: O(n log n)
    """
    # le test suivant dégraderait les performances
    # assert intervals == sorted(intervals)
    if intervals == []:
        return None
    center = intervals[len(intervals) // 2][0]
    L = []
    R = []
    C = []
    for I in intervals:
        if I[1] <= center:
            L.append(I)
        elif center < I[0]:
            R.append(I)
        else:
            C.append(I)
    by_low = sorted((I[0], I) for I in C)
    by_high = sorted((I[1], I) for I in C)
    IL = interval_tree(L)
    IR = interval_tree(R)
    return _Node(center, by_low, by_high, IL, IR)
dataset/ETHPy150Open jilljenn/tryalgo/tryalgo/interval_tree.py/interval_tree/original