Source code for tryalgo.max_interval_intersec

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


# snip{
# pylint: disable=bad-whitespace
[docs]def max_interval_intersec(S): """determine a value that is contained in a largest number of given intervals :param S: list of half open intervals :complexity: O(n log n), where n = len(S) """ B = ([(left, +1) for left, right in S] + [(right, -1) for left, right in S]) B.sort() c = 0 best = (c, None) for x, d in B: c += d if best[0] < c: best = (c, x) return best
# snip}