Rust

Tried to outsmart part 2 by not merging ranges but just subtracting overlapping ranges from the current range’s size, but then overlapping overlaps are subtracted more than once. So I ended up merging the ranges. They are kept in a list that is sorted by their starting position. Also, transforming the inclusive ranges in the input into exclusive ranges made things quite a bit easier.

View on github

use std::ops::Range;

fn parse_input(input: &str) -> (Vec<Range<u64>>, Vec<u64>) {
    let ranges: Vec<_> = input
        .lines()
        .take_while(|l| !l.is_empty())
        .map(|l| {
            let (a, b) = l.split_once('-').unwrap();
            a.parse().unwrap()..b.parse::<u64>().unwrap() + 1
        })
        .collect();
    let nums = input
        .lines()
        .skip(ranges.len() + 1)
        .map(|n| n.parse().unwrap())
        .collect();
    (ranges, nums)
}

fn part1(input: String) {
    let (ranges, nums) = parse_input(&input);
    let count = nums
        .iter()
        .filter(|n| ranges.iter().any(|r| r.contains(n)))
        .count();
    println!("{count}");
}

fn part2(input: String) {
    let (ranges, _) = parse_input(&input);
    // Ranges are added to this Vec always sorted by start and non-overlapping
    let mut merged: Vec<Range<u64>> = Vec::with_capacity(ranges.len());
    for r in ranges {
        // Find index of first intersecting range
        let first_int_o = merged.iter().position(|m| {
            // Intersection range (if any)
            let int_start = r.start.max(m.start);
            let int_end = r.end.min(m.end);
            int_start < int_end
        });
        if let Some(first_int) = first_int_o {
            // Exclusive
            let last_int = merged.len()
                - merged
                    .iter()
                    .rev()
                    .position(|m| {
                        let int_start = r.start.max(m.start);
                        let int_end = r.end.min(m.end);
                        int_start < int_end
                    })
                    .unwrap();
            // New range replacing all intersecting ranges
            let new = r.start.min(merged[first_int].start)..r.end.max(merged[last_int - 1].end);
            merged[first_int] = new;
            for i in (first_int + 1)..last_int {
                merged.remove(i);
            }
        } else {
            // Does not overlap with anything. Find index that keeps sorting
            let idx = merged
                .iter()
                .position(|m| m.start > r.start)
                .unwrap_or(merged.len());
            merged.insert(idx, r);
        }
    }
    let count = merged.iter().map(|r| r.end - r.start).sum::<u64>();
    println!("{count}");
}

util::aoc_main!();