Source code for tryalgo.intervals_union

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Union of intervals
jill-jênn vie et christoph dürr - 2014-2019
"""


# snip{
[docs]def intervals_union(S): """Union of intervals :param S: list of pairs (low, high) defining intervals [low, high) :returns: ordered list of disjoint intervals with the same union as S :complexity: O(n log n) """ E = [(low, -1) for (low, high) in S] E += [(high, +1) for (low, high) in S] nb_open = 0 last = None retval = [] for x, _dir in sorted(E): if _dir == -1: if nb_open == 0: last = x nb_open += 1 else: nb_open -= 1 if nb_open == 0: retval.append((last, x)) return retval
# snip}