Interval containment by sorting in Python
Sort by start and end, then compare each interval with its successors.
- File
interval_containment_sort.py, 42 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-containment-sort/. The authors are listed in prov/8YB754.jsonl.
"""Interval containment by sorting.
For each interval, find an interval of the family that contains it, or report
that it is maximal. Intervals are pairs (l, r) with l <= r, all of one type
(closed, half-open or open); the containment test l' <= l and r <= r' is the
same for every type. End points may be any comparable keys, so mixed types can
be encoded as (x, 0) or (x, 1) keys.
"""
from typing import Any, Optional, Sequence, Tuple
Interval = Tuple[Any, Any]
def interval_containment_sort(intervals: Sequence[Interval]) -> list[Optional[int]]:
"""Return parent[k]: the index of an interval that contains interval k, or None.
The intervals with parent None are exactly one copy of each maximal interval
(an interval no other interval properly contains). Among equal copies, the
copy with the smallest index is kept as maximal.
"""
n = len(intervals)
# Sort by left end ascending, then right end descending, then index.
# Two stable sorts; reverse=True keeps equal keys in their old order.
order = list(range(n)) # @line L1
order.sort(key=lambda k: intervals[k][1], reverse=True)
order.sort(key=lambda k: intervals[k][0])
parent: list[Optional[int]] = [None] * n # @line L2
best: Optional[int] = None
for k in order: # @line L3
if best is not None and intervals[k][1] <= intervals[best][1]: # @line L4
parent[k] = best # @line L5
else:
best = k # @line L6
return parent # @line L7
def has_nested_pair(intervals: Sequence[Interval]) -> bool:
"""Decide whether some interval contains another one (different index)."""
return any(p is not None for p in interval_containment_sort(intervals))
test_interval_containment_sort.py 82 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/interval-containment-sort/. The authors are listed in prov/8YB754.jsonl.
import random
from interval_containment_sort import has_nested_pair, interval_containment_sort
def contains(outer, inner):
return outer[0] <= inner[0] and inner[1] <= outer[1]
def check(intervals):
"""Check the parent array against the definition by brute force."""
parent = interval_containment_sort(intervals)
n = len(intervals)
assert len(parent) == n
for k in range(n):
p = parent[k]
if p is not None:
assert p != k
assert contains(intervals[p], intervals[k])
assert parent[p] is None # the container is a kept maximal interval
else:
# k is maximal and no smaller index holds an equal copy
for j in range(n):
if j == k:
continue
if contains(intervals[j], intervals[k]):
assert intervals[j] == intervals[k] and j > k
brute = any(j != k and contains(intervals[j], intervals[k]) for j in range(n) for k in range(n))
assert has_nested_pair(intervals) == brute
return parent
def test_example():
family = [(1, 4), (2, 3), (3, 6), (1, 2), (5, 6), (3, 6), (6, 8), (7, 8)]
assert check(family) == [None, 0, None, 0, 2, 2, None, 6]
def test_touching_cases():
# shared left end: nested
assert check([(1, 4), (1, 2)]) == [None, 0]
assert check([(1, 2), (1, 4)]) == [1, None]
# shared right end: nested
assert check([(3, 6), (5, 6)]) == [None, 0]
# touching at one point only: not nested
assert check([(3, 6), (6, 8)]) == [None, None]
assert not has_nested_pair([(1, 3), (3, 5)])
# duplicates: the first copy is kept
assert check([(2, 5), (2, 5), (2, 5)]) == [None, 0, 0]
# point intervals: nested only when equal
assert check([(4, 4), (1, 1), (4, 4)]) == [None, None, 0]
# a point at the end of an interval is inside it
assert check([(4, 4), (1, 4)]) == [1, None]
def test_edge_cases():
assert interval_containment_sort([]) == []
assert check([(0, 0)]) == [None]
assert not has_nested_pair([(1, 3), (2, 4), (3, 5)]) # a proper family
def test_mixed_types_with_keys():
# left key (x, 0) closed, (x, 1) open; right key (x, 1) closed, (x, 0) open
closed = ((1, 0), (3, 1)) # [1, 3]
half_open = ((1, 0), (3, 0)) # [1, 3)
open_ = ((1, 1), (3, 0)) # (1, 3)
assert check([half_open, closed]) == [1, None]
assert check([open_, half_open]) == [1, None]
assert check([closed, open_]) == [None, 0]
def test_random_against_brute_force():
rng = random.Random(8754)
for _ in range(800):
n = rng.randint(0, 12)
span = rng.choice([3, 6, 15])
family = []
for _ in range(n):
a, b = rng.randint(0, span), rng.randint(0, span)
family.append((min(a, b), max(a, b)))
check(family)
What the next level needs
- the tests did not run in this build