Advent of Code 2025 - Day 5Cafeteria

| Problem statement | Source code | Tags: Geometry

Part 1

I didn't do anything fancy: for each number, I iterate through all ranges to see if it falls in any of them. Technically, I can optimize this by sorting the ranges and using binary search, but the input size is small enough that it doesn't matter.

for line in parts[1].lines() {
    let num: u64 = line.parse().unwrap();
    if ranges.iter().any(|&(s, e)| num >= s && num <= e) {
        total += 1;
    }
}

Part 2

Now we wish to merge the ranges into a single list of disjoint intervals, and then count their total length. I sort the ranges by their start point, which puts mergeable intervals next to each other. For each additional interval, if it does not overlap with the previous one (start > last_end), then this segment is added completely to the total length. Otherwise, if it overlaps but extends the previous one (end > last_end), then only the non-overlapping part is added to the total length. Otherwise, the interval is completely contained in the previous one and does not contribute to the total length.

ranges.sort_by_key(|k| k.0);
let mut last_end = ranges[0].1;
let mut total = last_end - ranges[0].0 + 1;
for (start, end) in ranges.iter().skip(1) {
    if *start > last_end {
        total += end - start + 1;
        last_end = *end;
    } else if *end > last_end {
        total += end - last_end;
        last_end = *end;
    }
}