Interval piercing greedy in Python
Place a point at the earliest end point of the remaining intervals.
- File
interval_piercing_greedy.py, 44 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/interval-piercing-greedy/. The authors are listed in prov/V30M7R.jsonl.
"""Greedy piercing of intervals by the earliest right end.
kind is "closed" ([l, r], l <= r), "half-open" ([l, r), l < r) or "open"
((l, r), l < r). For closed intervals the points are right ends. For the other
types the greedy point is "just left of r"; the function returns a concrete
point of that group: max l for half-open, and the midpoint of max l and r for
open intervals.
"""
from typing import Sequence, Tuple
Interval = Tuple[float, float]
def interval_piercing_greedy(intervals: Sequence[Interval], kind: str = "closed") -> list[float]:
"""Return a smallest list of points such that every interval contains one."""
if kind not in ("closed", "half-open", "open"):
raise ValueError("kind must be closed, half-open or open")
order = sorted(range(len(intervals)), key=lambda k: intervals[k][1]) # @line L1
points: list[float] = [] # @line L2
p = None # the right end that opened the current group
max_l = None # the largest left end in the current group
for k in order: # @line L3
l, r = intervals[k]
pierced = p is not None and (l <= p if kind == "closed" else l < p) # @line L4
if not pierced:
p, max_l = r, l # @line L5
points.append(_point(p, max_l, kind)) # @line L6
else:
# The group point must also lie in this interval: move it right
# of l if needed (only for half-open and open intervals).
max_l = max(max_l, l)
points[-1] = _point(p, max_l, kind)
return points # @line L7
def _point(p, max_l, kind):
if kind == "closed":
return p
if kind == "half-open":
return max_l
return (max_l + p) / 2
test_interval_piercing_greedy.py 81 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/interval-piercing-greedy/. The authors are listed in prov/V30M7R.jsonl.
import itertools
import random
from interval_piercing_greedy import interval_piercing_greedy
def contains(iv, x, kind):
l, r = iv
if kind == "closed":
return l <= x <= r
if kind == "half-open":
return l <= x < r
return l < x < r
def pierces(points, intervals, kind):
return all(any(contains(iv, x, kind) for x in points) for iv in intervals)
def brute(intervals, kind, span):
"""Fewest points, searching the half-integer grid (enough for integer end points)."""
if not intervals:
return 0
grid = [h / 2 for h in range(0, 2 * span + 1)]
for size in range(1, len(intervals) + 1):
for pts in itertools.combinations(grid, size):
if pierces(pts, intervals, kind):
return size
raise AssertionError("unreachable")
def check(intervals, kind, span):
got = interval_piercing_greedy(intervals, kind)
assert pierces(got, intervals, kind)
assert len(got) == brute(intervals, kind, span)
return got
EXAMPLE = [(1, 4), (2, 3), (3, 6), (5, 7), (6, 8), (8, 9), (9, 10)]
def test_example():
assert check(EXAMPLE, "closed", 10) == [3, 7, 9]
assert check(EXAMPLE, "half-open", 10) == [2, 5, 6, 8, 9]
assert check(EXAMPLE, "open", 10) == [2.5, 5.5, 7.0, 8.5, 9.5]
def test_touching_cases():
assert check([(1, 3), (3, 5)], "closed", 5) == [3]
assert len(check([(1, 3), (3, 5)], "half-open", 5)) == 2
assert len(check([(1, 3), (3, 5)], "open", 5)) == 2
# equal right ends
assert check([(2, 5), (0, 5), (5, 5)], "closed", 5) == [5]
assert check([(2, 5), (0, 5)], "half-open", 5) == [2]
# point intervals (closed only): one point per distinct value
assert check([(4, 4), (1, 1), (4, 4)], "closed", 4) == [1, 4]
def test_edge_cases():
assert interval_piercing_greedy([]) == []
assert check([(0, 1)], "closed", 1) == [1]
assert check([(0, 1)], "half-open", 1) == [0]
assert check([(0, 1)], "open", 1) == [0.5]
nested = [(0, 6), (1, 5), (2, 4)]
assert len(check(nested, "open", 6)) == 1
def test_random_against_brute_force():
rng = random.Random(30)
for trial in range(900):
kind = ("closed", "half-open", "open")[trial % 3]
n = rng.randint(0, 6)
span = 5
ivs = []
for _ in range(n):
a = rng.randint(0, span - 1)
b = rng.randint(a + (0 if kind == "closed" else 1), span)
ivs.append((a, b))
check(ivs, kind, span)
What the next level needs
- the tests did not run in this build