import sys; sys.path.insert(0, str(__import__("pathlib").Path(__file__).resolve().parent))
from interval_cover import min_interval_cover

# basic
assert min_interval_cover([(0,5),(5,10)], 10) is not None
r = min_interval_cover([(0,5),(5,10)], 10)
assert len(r)==2
# impossible
assert min_interval_cover([(0,4),(5,10)], 10) is None
# single
assert min_interval_cover([(0,10)], 10) == [(0,10)]
# empty target
assert min_interval_cover([(0,5)], 0) == []
# greedy optimal check vs brute for small
import itertools
def brute(intervals,target):
    # min subset covering [0,target)
    best=None
    for r in range(1,len(intervals)+1):
        for combo in itertools.combinations(intervals,r):
            # check coverage
            cur=0
            # sort
            s=sorted(combo)
            ok=True
            for a,b in s:
                if a>cur: ok=False;break
                cur=max(cur,b)
            if ok and cur>=target:
                best=r; break
        if best: break
    return best
import random
random.seed(1)
for _ in range(2000):
    n=random.randint(1,6)
    ivs=[]
    for _ in range(n):
        a=random.randint(0,6); b=a+random.randint(1,4)
        ivs.append((a,b))
    t=random.randint(1,8)
    res=min_interval_cover(ivs,t)
    got = len(res) if res is not None else None
    # feasibility
    feas = any(True for _ in [0]) 
    # compute brute min if feasible
    b=brute(ivs,t)
    if b is None:
        assert res is None, (ivs,t,res)
    else:
        assert res is not None and len(res)==b, (ivs,t,res,b)
print("all ok")