"""Minimum number of intervals to cover [0, target).

Greedy: at each step, among intervals with start <= current coverage end,
pick the one extending furthest right. Returns list of chosen intervals
or None if full coverage impossible.
"""
from __future__ import annotations


def min_interval_cover(intervals, target):
    if target <= 0:
        return []
    ivs = sorted(intervals, key=lambda x: x[0])
    chosen = []
    cur_end = 0
    i = 0
    n = len(ivs)
    while cur_end < target:
        best_end = cur_end
        best = None
        # consider all intervals starting <= cur_end
        j = 0
        # find first not considered; use scanning from 0 each iteration is fine for correctness
        for iv in ivs:
            if iv[0] <= cur_end and iv[1] > best_end:
                best_end = iv[1]
                best = iv
        if best is None or best_end == cur_end:
            return None
        chosen.append(best)
        cur_end = best_end
        # remove used interval to avoid infinite loop? If best still best, next iteration best_end would equal cur_end -> None. Remove it.
        ivs = [x for x in ivs if x is not best]
    return chosen