# takes a list of (start, end) ranges and merges overlapping ones
def merge_overlapping_ranges(ranges: list[tuple[int, int]]) -> list[tuple[int, int]]:
    # sort ranges by start so that overlaps are adjacent
    ranges.sort(key=lambda r: r[0])
    merged_ranges = []

    # keep track of a current range that could be merged into
    curr_start, curr_end = ranges[0]
    for start, end in ranges:
        if curr_start <= start <= curr_end:
            # overlap, extend current range
            curr_end = max(curr_end, end)
        else:
            # no overlap, save current range and record the new one
            merged_ranges.append((curr_start, curr_end))
            curr_start, curr_end = start, end
    # finally, don't forget to add the last range that's being tracked
    merged_ranges.append((curr_start, curr_end))

    return merged_ranges

def part1(data: str):
    # split input
    freshness_data, ingredients_data = data.split("\n\n")

    # parse data
    freshness_ranges = [tuple(map(int, f.split('-'))) for f in freshness_data.splitlines()]
    freshness_ranges = merge_overlapping_ranges(freshness_ranges)   # optimization: merge overlapping ranges
    ingredients = [int(i) for i in ingredients_data.splitlines()]

    # checks if an ingredient is fresh
    # this could've been done with binary search, but linear search is simpler and fast enough
    def is_fresh(ingredient: int) -> bool:
        for start, end in freshness_ranges:
            if start <= ingredient <= end:
                # found
                return True
            if start > ingredient:
                # quit early since we are past any range that could've contained the ingredient
                return False
        return False

    # count all fresh ingredients
    return sum(is_fresh(i) for i in ingredients)

def part2(data: str):
    # split input
    freshness_data, _ = data.split("\n\n")

    # parse data
    freshness_ranges = [tuple(map(int, f.split('-'))) for f in freshness_data.splitlines()]
    freshness_ranges = merge_overlapping_ranges(freshness_ranges)   # merge overlapping ranges

    # return total count of fresh ingredients
    # we add +1 because both start and end are inclusive
    return sum(end - start + 1 for start, end in freshness_ranges)

sample = """3-5
10-14
16-20
12-18

1
5
8
11
17
32"""
assert part1(sample) == 3
assert part2(sample) == 14